DSAhardGraphs~35m

Five Stars

Problem

You just pulled off a heist in Los Santos and have a 5-star wanted level. The city road network is a directed weighted graph — each road has a travel time. You need to find the fastest escape route from your current location (node 0) to the city limits (node n-1) before the police close in.

Given n intersections numbered 0 to n-1 and a list of directed roads [u, v, time], return the minimum travel time to escape. If no escape route exists, return -1.

Examples

Example 1

Input: (3, [[0,2,100],[0,1,1],[1,2,1]])

Output: 2

Direct route 0→2 takes 100 seconds. Detour 0→1→2 takes only 2 seconds. BFS would wrongly return 100 (fewer hops). Dijkstra correctly returns 2.

Example 2

Input: (5, [[0,4,50],[0,1,2],[1,2,2],[2,3,2],[3,4,2]])

Output: 8

Direct escape takes 50 seconds. The 4-hop route through back streets takes only 8 seconds.

Example 3

Input: (4, [[0,3,1000],[0,1,10],[1,3,10]])

Output: 20

Direct escape costs 1000. Going through intersection 1 costs only 10+10=20.

Constraints

›2 <= n <= 500
›0 <= len(edges) <= 5000
›1 <= weight <= 10^6
›No negative weights
›No self-loops

Loading question…