Number of Ways to Arrive at Destination

medium dijkstra dp graph

Problem

A city has n intersections labeled 0 to n−1, joined by two-way roads where roads[i] = [u, v, t] means driving between u and v takes t minutes. There is at most one road between any pair of intersections, and every travel time is positive.

Starting at intersection 0, you want to reach intersection n−1 in the least total time. Count how many different routes achieve that minimum time, and return the count modulo 10⁹ + 7.

Inputn = 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]]

Output4

The fastest trip takes 7 minutes, and exactly four routes achieve it: 0→6, 0→4→6, 0→1→2→5→6, and 0→1→3→5→6.

n (intersections, 2–8)

roads ([u, v, time] list, JSON)

import heapq

MOD = 10**9 + 7

def count_paths(n, roads):
    adj = [[] for _ in range(n)]
    for u, v, w in roads:
        adj[u].append((v, w))
        adj[v].append((u, w))
    dist = [float("inf")] * n
    ways = [0] * n
    dist[0], ways[0] = 0, 1
    pq = [(0, 0)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                ways[v] = ways[u]
                heapq.heappush(pq, (nd, v))
            elif nd == dist[v]:
                ways[v] = (ways[v] + ways[u]) % MOD
    return ways[n - 1]

function countPaths(n, roads) {
  const MOD = 1_000_000_007;
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v, w] of roads) {
    adj[u].push([v, w]);
    adj[v].push([u, w]);
  }
  const dist = new Array(n).fill(Infinity);
  const ways = new Array(n).fill(0);
  dist[0] = 0; ways[0] = 1;
  const pq = [[0, 0]];               // [time, node]
  while (pq.length) {
    pq.sort((a, b) => b[0] - a[0]);  // poor man's min-heap
    const [d, u] = pq.pop();
    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];
}

int countPaths(int n, int[][] roads) {
    final int MOD = 1_000_000_007;
    List<long[]>[] adj = new List[n];
    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
    for (int[] r : roads) {
        adj[r[0]].add(new long[]{r[1], r[2]});
        adj[r[1]].add(new long[]{r[0], r[2]});
    }
    long[] dist = new long[n]; Arrays.fill(dist, Long.MAX_VALUE);
    int[] ways = new int[n];
    dist[0] = 0; ways[0] = 1;
    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    pq.add(new long[]{0, 0});
    while (!pq.isEmpty()) {
        long[] top = pq.poll();
        long d = top[0]; int u = (int) top[1];
        if (d > dist[u]) continue;
        for (long[] e : adj[u]) {
            int v = (int) e[0]; long nd = d + e[1];
            if (nd < dist[v]) {
                dist[v] = nd;
                ways[v] = ways[u];
                pq.add(new long[]{nd, v});
            } else if (nd == dist[v]) {
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
    return ways[n - 1];
}

int countPaths(int n, vector<vector<int>>& roads) {
    const int MOD = 1e9 + 7;
    vector<vector<pair<int,int>>> adj(n);
    for (auto& r : roads) {
        adj[r[0]].push_back({r[1], r[2]});
        adj[r[1]].push_back({r[0], r[2]});
    }
    vector<long long> dist(n, LLONG_MAX);
    vector<int> ways(n, 0);
    dist[0] = 0; ways[0] = 1;
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            long long 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];
}

Explanation

Finding the minimum travel time is classic Dijkstra. The twist is counting how many routes achieve it — and the key insight is that Dijkstra settles nodes in non-decreasing distance order, so we can piggyback a second array ways[v] that counts shortest routes into v, and it will be complete exactly when v is popped from the heap.

Relaxing an edge u → v with new time nd = dist[u] + w has two interesting cases. If nd < dist[v], we found a strictly faster way in, so every old route into v is obsolete: set dist[v] = nd and copy ways[v] = ways[u]. If nd == dist[v], we found a different, equally fast family of routes: add ways[v] += ways[u], keeping the sum modulo 10⁹ + 7 because counts grow exponentially with graph size.

This is really a DP over the shortest-path DAG: an edge belongs to the DAG when dist[u] + w == dist[v], and ways[v] is the sum of ways[u] over its DAG predecessors. Because all weights are positive, every such predecessor u has dist[u] < dist[v] and is settled before v — Dijkstra's pop order is exactly a valid evaluation order for the DP, so when v is finalized its count can never change again.

In the default example, node 1 settles at time 2, then nodes 2 and 3 both settle at time 5 via node 1. Node 5 is reached at time 6 through node 2, and then node 3 ties that time, so ways[5] = 1 + 1 = 2. Node 6 first gets the direct road at time 7, then node 4 ties it (ways[6] = 2), and finally node 5 ties it again contributing its 2 routes — ways[6] = 4, the answer.

With a binary heap, each edge causes at most one push per endpoint settlement, so the run time is O((n + e) log n), and the adjacency list plus the dist, ways, and heap arrays use O(n + e) space.

Time: O((n + e) log n) Space: O(n + e)