PPractick

The problem

A ride-hailing app wants to know how many different fastest routes exist from intersection 0 to intersection n − 1, since that affects how traffic spreads. Roads are undirected with positive travel times. Return the count modulo 10⁹ + 7. Extend Dijkstra with a ways counter. When a strictly shorter distance to v is found, v inherits ways[u]. When an equally short one is found, add ways[u] to ways[v]. Positive weights guarantee ways[u] is final when u is settled.

Example: 7 intersections (LeetCode's example) → 4 fastest routes, each taking 7 minutes.

Function signature

int countPaths(int n, const vector<array<int, 3>>& roads);  // roads {u, v, time}, undirected; modulo 1e9 + 7

Test cases

Input (n, roads)	Output	Explanation
(7, [[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	Four routes of length 7
(4, [[0,1,1],[0,2,1],[1,3,1],[2,3,1]])	2	Through 1 or through 2
(3, [[0,1,1],[1,2,1],[0,2,2]])	2	Direct, or via 1
(2, [[1,0,10]])	1
(1, [])	1	Already there

(Confirm: travel times are positive; the graph is connected; the answer is taken modulo 1,000,000,007.)

How interviewers phrase it

• "Return the number of ways you can travel from intersection 0 to intersection n − 1 in the shortest amount of time, modulo 10⁹ + 7" (LeetCode 1976).

Clarifying questions to ask

1. Are times strictly positive? (Yes, which matters for correctness.)
2. Undirected roads? (Yes.)
3. Can the count be huge? (Yes, so use modulo arithmetic.)

Follow-ups to expect

1. "How does the counting work?"
2. "Why must weights be positive?"
3. "Why skip stale heap entries?"
4. "Alternative?"
5. "Complexity?"

Related questions

• Djisktra's Algorithm Hard
• Why priority Queue is used in Djisktra's Algorithm Hard
• Path with minimum effort Hard
• Cheapest flight within K stops Hard
• Floyd warshall algorithm Hard
• Network Delay Time Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in