Get started

Number of Ways to Arrive at Destination — Medium Problem & Solution

A city has n intersections numbered 0 … n - 1 joined by bidirectional roads; roads[i] = [u, v, time] gives the time to drive that road.

Problem statement

A city has n intersections numbered 0 … n - 1 joined by bidirectional roads; roads[i] = [u, v, time] gives the time to drive that road.

You start at intersection 0 and want to reach intersection n - 1 in the shortest possible time. Return how many different routes achieve that time, modulo 10^9 + 7.

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: Four different routes all take 7 minutes.

Example 2

Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: Only one road.

Example 3

Input: n = 3, roads = [[0,1,1],[1,2,1],[0,2,2]]
Output: 2
Explanation: Two routes both take 2 minutes.

Constraints

  • 1 <= n <= 200
  • n - 1 <= roads.length <= n * (n - 1) / 2
  • roads[i].length == 3
  • 0 <= u, v <= n - 1
  • 1 <= time <= 1000
  • u != v
  • There is at most one road connecting any two intersections.
  • You can reach any intersection from any other intersection.

How to solve Number of Ways to Arrive at Destination

Dijkstra's algorithm with path counting. Alongside dist[v], keep ways[v]: when relaxing an edge, a strictly better distance replaces the count, and an equal distance adds to it.

Approach

  1. Set dist[0] = 0 and ways[0] = 1; everything else is infinity with 0 ways.
  2. Repeatedly finalise the unfinished node with the smallest distance.
  3. Relaxing u → v: if dist[u] + t < dist[v], set dist[v] and ways[v] = ways[u]; if equal, add ways[u] into ways[v] modulo 10^9 + 7.
  4. Return ways[n - 1].

Why it works

Counting works because a node's distance is final when it is popped: since every road takes positive time, no later discovery can shorten it, so every contribution it makes afterwards is genuinely on a shortest route. Only ways needs the modulus — dist is a real time and must stay exact, or comparisons between routes would go wrong.

Complexity

  • Time — O(n² + m) with a plain Dijkstra
  • Space — O(n + m)

Pitfalls

  • Reducing dist under the modulus destroys the comparisons; only ways is reduced.
  • Equal-distance routes must add counts, not overwrite them.
  • Roads are bidirectional, so each one goes into both adjacency lists.

Reference solution

Python

from typing import List
import heapq

def countPaths(n: int, roads: List[List[int]]) -> int:
    MOD = 1000000007
    adj = [[] for _ in range(n)]
    for u, v, t in roads:
        adj[u].append((v, t))
        adj[v].append((u, t))
    BIG = float('inf')
    dist = [BIG] * n
    ways = [0] * n
    dist[0] = 0
    ways[0] = 1
    heap = [(0, 0)]
    done = [False] * n
    while heap:
        d, u = heapq.heappop(heap)
        if done[u]:
            continue
        done[u] = True
        for v, t in adj[u]:
            if done[v]:
                continue
            nd = d + t
            if nd < dist[v]:
                dist[v] = nd
                ways[v] = ways[u]
                heapq.heappush(heap, (nd, v))
            elif nd == dist[v]:
                ways[v] = (ways[v] + ways[u]) % MOD
    return ways[n - 1]

JavaScript

var countPaths = function(n, roads) {
    var MOD = 1000000007, BIG = 1000000000, i, k;
    var adj = [];
    for (i = 0; i < n; i++) adj.push([]);
    for (i = 0; i < roads.length; i++) {
        adj[roads[i][0]].push([roads[i][1], roads[i][2]]);
        adj[roads[i][1]].push([roads[i][0], roads[i][2]]);
    }
    var dist = [], ways = [], done = [];
    for (i = 0; i < n; i++) { dist.push(BIG); ways.push(0); done.push(false); }
    dist[0] = 0;
    ways[0] = 1;
    for (var it = 0; it < n; it++) {
        var u = -1, best = BIG;
        for (i = 0; i < n; i++) {
            if (!done[i] && dist[i] < best) { best = dist[i]; u = i; }
        }
        if (u < 0) break;
        done[u] = true;
        for (k = 0; k < adj[u].length; k++) {
            var v = adj[u][k][0], t = adj[u][k][1];
            if (done[v]) continue;
            var nd = dist[u] + t;
            if (nd < dist[v]) {
                dist[v] = nd;
                ways[v] = ways[u];
            } else if (nd === dist[v]) {
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
    return ways[n - 1];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 195 dynamic programming problems · the whole catalogue