NeetCode #642LC-1976MediumAdvanced Graphs
← Back to All Problems#642 · #1976 · Number of Ways to Arrive at Destination(到达目的地的方案数)
📌 Problem Statement & Constraints
You are given
n intersections and roads[i] = [u, v, time] as undirected roads. Return the number of ways to travel from 0 to n-1 in the shortest time, modulo 10^9 + 7. Constraints: 1 <= n <= 200, 0 <= roads.length <= n * (n - 1) / 2, 1 <= time <= 10^9.💡 Core Algorithmic Approaches
- Dijkstra computes the shortest distance to each node, and a parallel
waysarray counts the shortest paths. - When a strictly shorter distance is found, the way count is replaced by the predecessor's count.
- When an equal distance is found, the counts are added.
- This is the standard shortest-path counting pattern.
💻 Benchmark Python3 Implementation
class Solution:
def countPaths(self, n: int, roads: List[List[int]]) -> int:
import heapq
from collections import defaultdict
MOD = 10 ** 9 + 7
g = defaultdict(list)
for u, v, w in roads:
g[u].append((v, w))
g[v].append((u, w))
dist = [float("inf")] * n
ways = [0] * n
dist[0] = 0
ways[0] = 1 # one way to be at the start
h = [(0, 0)]
while h:
d, node = heapq.heappop(h)
if d > dist[node]:
continue # stale entry
for nxt, w in g[node]:
nd = d + w
if nd < dist[nxt]:
dist[nxt] = nd
ways[nxt] = ways[node] # a new shortest path
heapq.heappush(h, (nd, nxt))
elif nd == dist[nxt]:
ways[nxt] = (ways[nxt] + ways[node]) % MOD # another shortest path
return ways[n - 1] % MOD⚡ Complexity Deep Dive
⏱️ Time Complexity
O(E log V): each edge is relaxed once.
💾 Space Complexity
O(V + E) for the graph and the arrays.
⚠️ Interview Pitfalls & Follow-ups
- Adding ways when the distance is strictly smaller: the count must be replaced.
- Forgetting the stale-entry check: a node could be processed with an outdated distance, corrupting the counts.
- Not taking the modulo: the count can be enormous.
- Using BFS: the weights differ, so distances are not proportional to edge counts.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.