⚡Flashcard Drill➔
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

  1. Dijkstra computes the shortest distance to each node, and a parallel ways array counts the shortest paths.
  2. When a strictly shorter distance is found, the way count is replaced by the predecessor's count.
  3. When an equal distance is found, the counts are added.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems