Roads on the Fastest Routes

Hard

A town has stops stops numbered from 0 to stops - 1, linked by two-way roads: roads[i] = [a, b, w] is a road between a and b that takes w minutes to drive. The town may be disconnected. Consider every fastest route from stop 0 to stop stops - 1. Return an array answer where answer[i] is True if road i lies on at least one fastest route and False otherwise. If stops - 1 cannot be reached, every value is False.

Example 1

stops=5, roads=[[0, 1, 2], [1, 4, 5], [0, 2, 3], [2, 4, 4], [2, 3, 1], [3, 4, 2]] → [False, False, True, False, True, True]

The fastest time to stop 4 is 6, along 0 → 2 → 3 → 4 (3 + 1 + 2). The route 0 → 1 → 4 takes 7, and so does 0 → 2 → 4, so roads 0, 1 and 3 are not used.

Example 2

stops=4, roads=[[0, 1, 1], [1, 3, 1], [0, 2, 1], [2, 3, 1]] → [True, True, True, True]

There are two fastest routes, 0 → 1 → 3 and 0 → 2 → 3, both taking 2. Together they use all four roads.

Example 3

stops=3, roads=[[0, 1, 7]] → [False]

Stop 2 cannot be reached, so no road qualifies.

Constraints

2 ≤ stops ≤ 5 · 10⁴
1 ≤ len(roads) ≤ min(5 · 10⁴, stops · (stops - 1) / 2)
roads[i] = [a, b, w], 0 ≤ a, b < stops, a ≠ b
1 ≤ w ≤ 10⁵
At most one road joins any two stops

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Graph Shortest Path Heap (Priority Queue)

Similar problems

Ball Into the Hole Hard Shortest Path of a Rolling Ball Medium Broadcast Reach Time Medium Cheapest Trip With Few Layovers Medium Repaint Arrows to Reach the Exit Hard

Input

stops=5, roads=[[0, 1, 2], [1, 4, 5], [0, 2, 3], [2, 4, 4], [2, 3, 1], [3, 4, 2]]

Expected

[False, False, True, False, True, True]

Run checks the first 3 tests in your browser. Submit checks all 70 tests on the server, hidden ones included.