Number of Ways to Arrive at Destination

Problem (restated)

n intersections (0 … n-1) and bidirectional roads [u, v, time]. Return how many shortest-time paths go from 0 to n-1, modulo 10^9+7.

Intuition

Run Dijkstra for shortest times, and piggy-back a ways[] array. When you find a strictly better time to v, copy ways[u]. When you find another path with the same time, add ways[u].

Approaches

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 */
export function countPaths(n: number, roads: number[][]): number {
  const MOD = 1_000_000_007;
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, t] of roads) {
    adj[u]!.push([v, t]);
    adj[v]!.push([u, t]);
  }
  const dist = new Array<number>(n).fill(Infinity);
  const ways = new Array<number>(n).fill(0);
  dist[0] = 0;
  ways[0] = 1;
  const pq: [number, number][] = [[0, 0]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, u] = pq.shift()!;
    if (d > dist[u]!) continue;
    for (const [v, w] of adj[u]!) {
      const nd = d + w;
      if (nd < dist[v]!) {
        dist[v] = nd;
        ways[v] = ways[u]!;
        pq.push([nd, v]);
      } else if (nd === dist[v]) {
        ways[v] = (ways[v]! + ways[u]!) % MOD;
      }
    }
  }
  return ways[n - 1]!;
}

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 */
export function countPaths(n: number, roads: number[][]): number {
  const MOD = 1_000_000_007;
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, t] of roads) {
    adj[u]!.push([v, t]);
    adj[v]!.push([u, t]);
  }
  const dist = new Array<number>(n).fill(Infinity);
  const ways = new Array<number>(n).fill(0);
  dist[0] = 0;
  ways[0] = 1;
  const pq: [number, number][] = [[0, 0]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, u] = pq.shift()!;
    if (d > dist[u]!) continue;
    for (const [v, w] of adj[u]!) {
      const nd = d + w;
      if (nd < dist[v]!) {
        dist[v] = nd;
        ways[v] = ways[u]!;
        pq.push([nd, v]);
      } else if (nd === dist[v]) {
        ways[v] = (ways[v]! + ways[u]!) % MOD;
      }
    }
  }
  return ways[n - 1]!;
}

Template connection

Dijkstra, with an extra ways[] that updates on a strict improvement (copy) or a tie (add). The heap still keys on distance only.

Reflection

• Dijkstra keeps the shortest time. A strictly shorter path replaces the count. An equal path adds to it. Reduce modulo 10**9 + 7.
• The source has time 0 and 1 way. A longer path does not count. A zero-weight edge adds another equal path. Do not push again on the equal case.
• Read ways[n - 1] after the loop. The first pop of the destination can still be missing a later equal-cost path.