Number of Ways to Arrive at Destination

MediumGraphs · Dijkstra + Path Counting DP🧩 Tree & Graph DP LeetCode #1976 ↗Updated Oct 30, 2026

Problem

A city has n intersections 0..n-1 joined by two-way roads, where roads[i] = [u, v, time]. Every intersection is reachable. Count how many different routes go from 0 to n-1 using the minimum possible total time, and return that count modulo 10⁹+7.

Inputn=4, roads=[[0,1,1],[0,2,1],[1,3,1],[2,3,1]]Output2

Inputn=4, roads=[[0,1,1],[1,2,1],[0,2,2],[2,3,5],[0,3,9]]Output2

Inputn=1, roads=[]Output1

1 ≤ n ≤ 200 · n-1 ≤ roads.length ≤ n(n-1)/2 · 1 ≤ time ≤ 10⁹ · at most one road per pair · answer mod 10⁹+7

Try it yourself

Java

class Solution {
    public int countPaths(int n, int[][] roads) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

With positive weights, every shortest route to v ends with an edge u→v where dist[u] + w = dist[v]. So ways[v] = Σ ways[u] over those “tight” edges — and Dijkstra pops nodes in exactly the order that makes this sum final.

PatternTree & Graph DP

Instinct A node's best answer depends only on its children's answers - post-order DFS that returns a tiny tuple of states per node.

Memory hack Kids report up, parent decides - every subtree hands its parent a small report card, and the parent never re-reads the kids' homework.

Open the Tree & Graph DP guide →

Approaches

Brute ForceDFS over All Simple Paths

Time O(n!)Space O(n²)

Positive weights mean a shortest route never repeats a node, so enumerate every simple path from 0 with backtracking. Keep the best total seen: a strictly shorter arrival resets the counter, an equal one increments it, and any partial path already longer than the best is cut off.

Java

private static final int MOD = 1_000_000_007;
private long best;
private long ways;

public int countPaths(int n, int[][] roads) {
    long[][] w = new long[n][n]; // 0 = no road
    for (int[] r : roads) {
        w[r[0]][r[1]] = r[2];
        w[r[1]][r[0]] = r[2];
    }
    best = Long.MAX_VALUE;
    ways = 0;
    dfs(0, n - 1, 0L, new boolean[n], w);
    return (int) ways;
}

private void dfs(int u, int target, long dist, boolean[] onPath, long[][] w) {
    if (dist > best) return; // already slower than the best route
    if (u == target) {
        if (dist < best) {
            best = dist;
            ways = 0;
        }
        ways = (ways + 1) % MOD;
        return;
    }
    onPath[u] = true;
    for (int v = 0; v < w.length; v++)
        if (w[u][v] > 0 && !onPath[v]) dfs(v, target, dist + w[u][v], onPath, w);
    onPath[u] = false;
}

Easy to trust and great for testing, but the number of simple paths explodes.

BetterFloyd–Warshall, then Count in Distance Order

Time O(n³)Space O(n²)

Split the job in two. First get exact shortest times with Floyd–Warshall. Then sort nodes by dist[0][v]: a predecessor on a shortest route is always strictly closer, so processing in that order lets ways[v] sum the already-final ways[u] of every tight edge.

Java

private static final int MOD = 1_000_000_007;

public int countPaths(int n, int[][] roads) {
    final long INF = Long.MAX_VALUE / 4;
    long[][] w = new long[n][n]; // direct road time, 0 = no road
    long[][] d = new long[n][n]; // shortest time between every pair
    for (long[] row : d) Arrays.fill(row, INF);
    for (int i = 0; i < n; i++) d[i][i] = 0;
    for (int[] r : roads) {
        w[r[0]][r[1]] = w[r[1]][r[0]] = r[2];
        d[r[0]][r[1]] = d[r[1]][r[0]] = r[2];
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];

    // Closer nodes first, so every predecessor is finished before its successor
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Long.compare(d[0][a], d[0][b]));
    long[] ways = new long[n];
    ways[0] = 1;
    for (int v : order)
        for (int u = 0; u < n; u++)
            if (w[u][v] > 0 && d[0][u] + w[u][v] == d[0][v])
                ways[v] = (ways[v] + ways[u]) % MOD;
    return (int) ways[n - 1];
}

Polynomial and simple, but computes all-pairs distances when only one source matters.

OptimalDijkstra with a Ways Array

Time O((n + E) log n)Space O(n + E)

Run Dijkstra from 0 and count while relaxing. A strictly shorter path to v replaces ways[v] with ways[u]; an equally short one adds ways[u]. When u is popped, all its tight predecessors were popped earlier (positive weights), so ways[u] is already final.

Java

private static final int MOD = 1_000_000_007;

public int countPaths(int n, int[][] roads) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] r : roads) {
        adj.get(r[0]).add(new int[]{r[1], r[2]});
        adj.get(r[1]).add(new int[]{r[0], r[2]});
    }
    long[] dist = new long[n];
    long[] ways = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[0] = 0;
    ways[0] = 1;
    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    pq.offer(new long[]{0, 0});
    while (!pq.isEmpty()) {
        long[] top = pq.poll();
        int u = (int) top[1];
        if (top[0] > dist[u]) continue; // stale entry
        for (int[] e : adj.get(u)) {
            int v = e[0];
            long nd = dist[u] + e[1];
            if (nd < dist[v]) {          // strictly better: restart the count
                dist[v] = nd;
                ways[v] = ways[u];
                pq.offer(new long[]{nd, v});
            } else if (nd == dist[v]) {  // another equally fast route
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
    return (int) ways[n - 1];
}

One single-source pass: the standard answer for counting shortest paths.

Pro tip

Store distances as long: 199 roads of 10⁹ each overflow int and silently corrupt the equality test.

At a glance

Level	Approach	Time	Space
Brute Force	DFS over All Simple Paths	`O(n!)`	`O(n²)`
Better	Floyd–Warshall, then Count in Distance Order	`O(n³)`	`O(n²)`
Optimal	Dijkstra with a Ways Array	`O((n + E) log n)`	`O(n + E)`

Common pitfalls

Using int distances — sums reach ~2·10¹¹ and overflow.
Adding to ways[v] on a strictly shorter path instead of resetting it.
Comparing floating/approximate distances or skipping the stale-entry check, which double-counts.

Interview tips

Say it upfront: “Dijkstra plus a DP on the shortest-path DAG”.
Explain why positive weights guarantee ways[u] is final when u is popped.
Mention the modulo and long distances before you start coding.

Pattern

Count shortest paths → Dijkstra/BFS that keeps a ways[] array: reset on improvement, add on tie.

My notes saved in this browser