This is a classic variation of the shortest path problem where we care not just about the cost of the path, but the multiplicity of optimal paths.

Brute Force Approach for Number of Ways to Arrive at Destination

A naive approach to solving Number of Ways to Arrive at Destination involves finding every possible simple path from the source to the destination, calculating the total time for each, identifying the minimum time, and counting how many paths match that minimum.

This is typically implemented using Depth First Search (DFS) or backtracking:

1. Start at node 0.
2. Recursively visit all unvisited neighbors, accumulating the total travel time.
3. If node n-1 is reached, record the path duration.
4. Once all paths are explored, scan the list of durations to find the minimum and count its frequency.

Pseudo-code for Brute Force

text
function dfs(current_node, current_time, visited):
    if current_node == destination:
        paths.add(current_time)
        return

    visited.add(current_node)
    for neighbor, weight in adj[current_node]:
        if neighbor not in visited:
            dfs(neighbor, current_time + weight, visited)
    visited.remove(current_node)

Why this fails

The time complexity of this approach is factorial, roughly $O(N!)$, because the number of simple paths in a graph can be exponential relative to the number of nodes. With $N$ up to 200, exploring all paths is computationally impossible and will immediately result in a Time Limit Exceeded (TLE) error. We need a polynomial-time solution, specifically one that builds upon shortest path algorithms.

Core Insight for Number of Ways to Arrive at Destination

The core insight for solving LeetCode 1976 efficiently lies in the property of optimal substructure found in shortest path algorithms.

In standard Dijkstra's algorithm, we greedily process nodes based on the shortest known distance from the source. This processing order guarantees that when we extract a node u from the priority queue, we have found the absolute shortest time to reach u.

To count the number of ways, we can maintain two arrays instead of one:

1. dist[i]: The shortest time found so far to reach node i.
2. ways[i]: The number of ways to reach node i in exactly dist[i] time.

The logic for updating these arrays relies on the relaxation step:

• Case 1: A strictly shorter path is found. If we travel from u to v and find that dist[u] + weight < dist[v], it means all previous paths to v are suboptimal. We update dist[v] to the new shorter time and reset ways[v] to equal ways[u].
• Case 2: An equal length path is found. If dist[u] + weight == dist[v], it means we have found an alternative path to v that is just as good as the one already recorded. We add ways[u] to the existing ways[v].

Visual Description: Imagine the algorithm as a wave spreading from the source. The priority queue ensures the wave expands uniformly by time. When the wave reaches a node v from multiple directions (neighbors) at the exact same minimal time moment, the "flow" (number of ways) from those neighbors merges at v. If the wave arrives later from another direction, that path is ignored.

Algorithm Strategy: Graph - Shortest Path (Dijkstra's Algorithm)

We will implement a modified version of Dijkstra's algorithm.

1. State Representation:

   • Use a dist array initialized to infinity, with dist[0] = 0.
   • Use a ways array initialized to 0, with ways[0] = 1 (there is one way to be at the start: doing nothing).
   • Use a Min-Heap (Priority Queue) to store pairs (current_time, u).

2. Priority Queue Processing:

   • Extract the node u with the smallest current_time.
   • If current_time is greater than dist[u], this is an outdated entry (we found a faster way to u previously); skip it.

3. Relaxation & Counting:

   • Iterate through all neighbors v of u with edge weight time.
   • Calculate new_time = current_time + time.
   • Strict Improvement: If new_time < dist[v]:
     • Update dist[v] = new_time.
     • Set ways[v] = ways[u].
     • Push (new_time, v) to the heap.
   • Equal Path: If new_time == dist[v]:
     • Update ways[v] = (ways[v] + ways[u]) % MOD.
     • Do not push to the heap. The node v is already in the queue (or processed) with the correct optimal distance; we simply accumulate the count.

4. Result:

   • After the queue is empty, ways[n-1] contains the answer.

Execution Flow

Let's trace the logic with a simplified graph: Nodes 0, 1, 2. Edges: (0->1, cost 2), (0->2, cost 5), (1->2, cost 3).

1. Initialization:

   • dist = [0, inf, inf]
   • ways = [1, 0, 0]
   • PQ: [(0, 0)]

2. Pop (0, 0):

   • Neighbors of 0: Node 1 (cost 2), Node 2 (cost 5).
   • Process Node 1: 0 + 2 < inf. Update dist[1] = 2. Set ways[1] = ways[0] = 1. Push (2, 1).
   • Process Node 2: 0 + 5 < inf. Update dist[2] = 5. Set ways[2] = ways[0] = 1. Push (5, 2).
   • PQ: [(2, 1), (5, 2)]

3. Pop (2, 1):

   • Neighbors of 1: Node 2 (cost 3).
   • Process Node 2: 2 + 3 = 5.
   • Check against dist[2] (which is 5).
   • 5 == 5: This is an equal shortest path.
   • Update ways[2] = ways[2] + ways[1] = 1 + 1 = 2.
   • Do not push to PQ.
   • PQ: [(5, 2)]

4. Pop (5, 2):

   • 5 matches dist[2]. Process neighbors (none in this example).

5. Termination:

   • PQ empty. Result is ways[2] = 2.

Proof of Correctness

The correctness relies on the invariant of Dijkstra's algorithm: nodes are extracted from the priority queue in non-decreasing order of their shortest path distances.

When we extract a node u with distance d, we are guaranteed that d is the shortest possible time to reach u. Because edge weights are positive, any path to u discovered later must have a distance $\ge d$.

• Since we process u's neighbors immediately, we propagate the count ways[u] to any neighbor v that lies on a shortest path extending from u.
• If multiple predecessors u1, u2 offer paths to v with the same minimal length, the condition new_time == dist[v] ensures we sum up ways[u1] + ways[u2] + ....
• The modulo operation distributes over addition, ensuring the count remains correct under modulo arithmetic.

Reference Implementation

C++ Solution for LeetCode 1976

cpp
#include <vector>
#include <queue>
#include <limits>

using namespace std;

class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        // Adjacency list: node -> vector of {neighbor, time}
        vector<vector<pair<int, int>>> adj(n);
        for (const auto& road : roads) {
            adj[road[0]].push_back({road[1], road[2]});
            adj[road[1]].push_back({road[0], road[2]});
        }

        // dist array to track shortest time, initialized to infinity
        // Using long long because total time can exceed 2^31 - 1
        vector<long long> dist(n, numeric_limits<long long>::max());
        
        // ways array to track number of shortest paths
        vector<long long> ways(n, 0);
        
        dist[0] = 0;
        ways[0] = 1;
        
        long long MOD = 1e9 + 7;
        
        // Min-heap storing {current_time, node}
        // Use greater<> for min-heap
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        pq.push({0, 0});
        
        while (!pq.empty()) {
            long long d = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            
            // If we found a shorter way to u already, skip
            if (d > dist[u]) continue;
            
            for (auto& edge : adj[u]) {
                int v = edge.first;
                int time = edge.second;
                
                // Case 1: Found a strictly shorter path
                if (dist[u] + time < dist[v]) {
                    dist[v] = dist[u] + time;
                    ways[v] = ways[u];
                    pq.push({dist[v], v});
                }
                // Case 2: Found another path with the same shortest duration
                else if (dist[u] + time == dist[v]) {
                    ways[v] = (ways[v] + ways[u]) % MOD;
                }
            }
        }
        
        return ways[n - 1];
    }
};

Java Solution for LeetCode 1976

java
import java.util.*;

class Solution {
    public int countPaths(int n, int[][] roads) {
        // Build adjacency list
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] road : roads) {
            adj.get(road[0]).add(new int[]{road[1], road[2]});
            adj.get(road[1]).add(new int[]{road[0], road[2]});
        }

        // Distances array (use long to prevent overflow)
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        
        // Ways array
        long[] ways = new long[n];
        
        dist[0] = 0;
        ways[0] = 1;
        long MOD = 1_000_000_007;

        // PriorityQueue stores {current_time, node}
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.offer(new long[]{0, 0});

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long d = current[0];
            int u = (int) current[1];

            if (d > dist[u]) continue;

            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                int time = edge[1];

                // Found a shorter path
                if (dist[u] + time < dist[v]) {
                    dist[v] = dist[u] + time;
                    ways[v] = ways[u];
                    pq.offer(new long[]{dist[v], v});
                } 
                // Found an equal path
                else if (dist[u] + time == dist[v]) {
                    ways[v] = (ways[v] + ways[u]) % MOD;
                }
            }
        }

        return (int) ways[n - 1];
    }
}

Python Solution for LeetCode 1976

python
import heapq
import sys

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        adj = [[] for _ in range(n)]
        for u, v, time in roads:
            adj[u].append((v, time))
            adj[v].append((u, time))
            
        # dist array initialized to infinity
        dist = [float('inf')] * n
        # ways array initialized to 0
        ways = [0] * n
        
        dist[0] = 0
        ways[0] = 1
        
        MOD = 10**9 + 7
        
        # Priority queue stores (time, node)
        pq = [(0, 0)]
        
        while pq:
            d, u = heapq.heappop(pq)
            
            # If current distance is greater than shortest found, skip
            if d > dist[u]:
                continue
            
            for v, time in adj[u]:
                if dist[u] + time < dist[v]:
                    dist[v] = dist[u] + time
                    ways[v] = ways[u]
                    heapq.heappush(pq, (dist[v], v))
                elif dist[u] + time == dist[v]:
                    ways[v] = (ways[v] + ways[u]) % MOD
                    
        return ways[n - 1]