Number of Ways to Reach Destination
in Shortest Time

Problem Statement

You are in a city with n intersections (numbered from 0 to n - 1) connected by bidirectional roads. Each road connects two intersections u and v and takes time minutes to travel.

You are given:

• An integer n — the number of intersections
• A 2D array roads where each entry is [u, v, time]

Your goal is to determine how many different ways you can travel from intersection 0 (source) to intersection n - 1 (destination) in the shortest possible time.

Return the number of such shortest paths modulo 10⁹ + 7.

Algorithm Steps

1. Create an adjacency list from the roads array.
2. Initialize dist array to store shortest time to each node (set all to Infinity except source).
3. Initialize ways array to store number of ways to reach each node (set all to 0 except source).
4. Use a priority queue (min-heap) and start from node 0 with time 0.
5. While the queue is not empty:
1. Pop the node with minimum current time.
2. For each neighbor of this node:
1. If a new shorter time is found, update dist and set ways to the current node's ways.
2. If the same time is found, increment ways by current node's ways.
6. Return ways[n - 1] % (10⁹ + 7).

Code

function countPaths(n, roads) {
  const MOD = 1e9 + 7;
  const adj = Array.from({ length: n }, () => []);

  for (const [u, v, t] of roads) {
    adj[u].push([v, t]);
    adj[v].push([u, t]);
  }

  const dist = Array(n).fill(Infinity);
  const ways = Array(n).fill(0);
  const minHeap = [[0, 0]]; // [time, node]

  dist[0] = 0;
  ways[0] = 1;

  while (minHeap.length > 0) {
    minHeap.sort((a, b) => a[0] - b[0]); // simple priority queue
    const [time, node] = minHeap.shift();

    for (const [nei, t] of adj[node]) {
      const newTime = time + t;
      if (newTime < dist[nei]) {
        dist[nei] = newTime;
        ways[nei] = ways[node];
        minHeap.push([newTime, nei]);
      } else if (newTime === dist[nei]) {
        ways[nei] = (ways[nei] + ways[node]) % MOD;
      }
    }
  }

  return ways[n - 1];
}

const 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]];
console.log("Number of shortest paths from 0 to 6:", countPaths(7, roads));