You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.

You are given an integer n and an array roads where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know how many ways you can travel from intersection 0 to intersection n - 1 in the shortest amount of time.

Return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo 10^9 + 7.

Thinking Process

You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.

You are given an integer n and an array roads where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know how many ways you can travel from intersection 0 to intersection n - 1 in the shortest amount of time.

  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Examples

Example 1:

Input: 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]]
Output: 4
Explanation: The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➜ 1 ➜ 2 ➜ 5 ➜ 6
- 0 ➜ 1 ➜ 3 ➜ 5 ➜ 6
- 0 ➜ 4 ➜ 6
- 0 ➜ 6

Example 2:

Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.

Constraints

  • 1 <= n <= 200
  • n - 1 <= roads.length <= n * (n - 1) / 2
  • roads[i].length == 3
  • 0 <= ui, vi <= n - 1
  • 1 <= timei <= 10^9
  • ui != vi
  • There is at most one road connecting any two intersections.
  • You can reach any intersection from any other intersection.

Dijkstra’s Template

Here’s the general template for Dijkstra’s algorithm with path counting:

int countShortestPaths(int n, vector<vector<pair<int, int>>>& adjList, int start, int end) {
    const int MOD = 1e9 + 7;
    const long long INF = LLONG_MAX;
    
    // Distance and path count arrays
    vector<long long> dist(n, INF);
    vector<int> pathCount(n, 0);
    
    // Priority queue: (distance, node)
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    
    // Initialize start node
    dist[start] = 0;
    pathCount[start] = 1;
    pq.emplace(0, start);
    
    while (!pq.empty()) {
        auto [currDist, currNode] = pq.top();
        pq.pop();
        
        // Skip if outdated (already found shorter path)
        if (currDist > dist[currNode]) continue;
        
        // Explore neighbors
        for (auto& [neighbor, weight] : adjList[currNode]) {
            long long newDist = currDist + weight;
            
            // Found shorter path: update distance and reset count
            if (newDist < dist[neighbor]) {
                dist[neighbor] = newDist;
                pathCount[neighbor] = pathCount[currNode];
                pq.emplace(newDist, neighbor);
            }
            // Found equal path: add to count
            else if (newDist == dist[neighbor]) {
                pathCount[neighbor] = (pathCount[neighbor] + pathCount[currNode]) % MOD;
            }
        }
    }
    
    return pathCount[end];
}

Key Template Components:

  1. Data Structures:
    • dist[i]: Shortest distance to node i
    • pathCount[i]: Number of shortest paths to node i
    • Priority queue: Min-heap for Dijkstra’s
  2. Initialization:
    • Start node: dist[start] = 0, pathCount[start] = 1
    • All other nodes: dist[i] = INF, pathCount[i] = 0
  3. Main Loop:
    • Extract minimum distance node
    • Skip outdated entries
    • Update neighbors:
      • Shorter: Update distance, reset count
      • Equal: Accumulate count
  4. Modulo: Apply MOD to prevent overflow

Complexity

Time Complexity: O((V + E) log V)

  • Priority queue operations: O(E log V) - each edge processed once
  • Graph traversal: O(V + E) - visit all nodes and edges
  • Total: O((V + E) log V) where V = n, E = number of roads

Space Complexity: O(V + E)

  • Adjacency list: O(E) - store all edges
  • Distance array: O(V) - store distances for all nodes
  • Path count array: O(V) - store counts for all nodes
  • Priority queue: O(V) - at most V nodes in queue
  • Total: O(V + E)

Key Points

  1. Dijkstra’s Algorithm: Finds shortest paths in weighted graphs with non-negative edges
  2. Path Counting: Track number of ways to reach each node with shortest distance
  3. Multiple Paths: When multiple paths have same distance, accumulate counts
  4. Modulo Arithmetic: Handle large numbers with 10^9 + 7
  5. Bidirectional Graph: Roads are undirected (both directions)
  6. Outdated Skip: Skip nodes with outdated distances in priority queue

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Tags

Dijkstra's Algorithm, Shortest Path, Graph, Dynamic Programming, Path Counting, Medium

Key Takeaways

  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.

References

Template Reference