Graph Traversal and Shortest Path

HardPython

Problem

Redesign Health is evaluating care journeys across services such as intake, clinical review, diagnostics, and treatment. Given a directed graph of service transitions, find the minimum total transition time from a starting service to a destination when one transition may use a virtual-care credit and therefore cost zero minutes.

You may use the credit at most once, or not use it. Return both the minimum time and the corresponding sequence of service IDs. If the destination cannot be reached, return [-1, []].

Formal Specification

Implement fastest_care_path(n, edges, start, end), where n is the number of services labeled 0 through n - 1, and each edges entry is [from_service, to_service, minutes]. Edges are directed, and multiple edges between the same services are allowed. Return [minimum_minutes, path], where path is a list of service IDs from start to end.

Constraints

1 <= n <= 100,000
0 <= len(edges) <= 200,000
0 <= from_service, to_service < n
0 <= minutes <= 10,000
All transition times are nonnegative

Function Signature

def fastest_care_path(n, edges, start, end):

You may use the credit at most once, or not use it. Return both the minimum time and the corresponding sequence of service IDs. If the destination cannot be reached, return [-1, []].