Shortest Safe Route Counter
Preview mode. Log in to edit, run, submit, and save progress.
Shortest Safe Route Counter
A logistics graph has n checkpoints and bidirectional roads with positive travel times. Dispatch starts at checkpoint 0 and wants to reach checkpoint n - 1. A route is shortest if its total travel time is equal to the minimum possible travel time between those two checkpoints. Count how many distinct shortest routes exist. Because the count can be large, return it modulo 1000000007. Input Format: You are given n and an array roads, where each road is [u, v, time]. Output Format: Return the number of distinct shortest routes from checkpoint 0 to checkpoint n - 1, modulo 1000000007.
Examples
n = 7 roads = [[0, 6, 7], [0, 1, 2], [1, 2, 3], [1, 3, 3], [6, 3, 3], [3, 5, 1], [6, 5, 1], [2, 5, 1], [0, 4, 5], [4, 6, 2]]
4
Explanation: The shortest travel time from hub 0 to hub 6 is 7. There are 4 route(s) achieving that time, so the output is 4.
Approach hint
Dijkstra gives shortest distances.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.