Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Number of Ways to Arrive at Destination

MEDIUMProblemSolveExternal Links

Description

You are in a city with n intersections numbered from 0 to n - 1, connected by bidirectional roads. Each road between two intersections has a travel time in minutes.

You want to travel from intersection 0 to intersection n - 1 in the shortest possible time. However, there may be multiple routes that all achieve this minimum travel time.

Return the number of ways you can travel from intersection 0 to intersection n - 1 using the minimum travel time. Since the answer may be very large, return it modulo 10^9 + 7.

The road network is connected (you can reach any intersection from any other), and there is at most one road directly connecting any two intersections.

Weighted undirected graph with 4 nodes showing three shortest paths from node 0 to node 3, all with total weight 6
Weighted undirected graph with 4 nodes showing three shortest paths from node 0 to node 3, all with total weight 6

Examples

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: The shortest time from intersection 0 to intersection 6 is 7 minutes. There are exactly 4 routes that achieve this:

  1. 0 → 6 (direct road, time 7)
  2. 0 → 4 → 6 (time 5 + 2 = 7)
  3. 0 → 1 → 2 → 5 → 6 (time 2 + 3 + 1 + 1 = 7)
  4. 0 → 1 → 3 → 5 → 6 (time 2 + 3 + 1 + 1 = 7)

Any other route from 0 to 6 takes more than 7 minutes.

Example 2

Input: n = 4, roads = [[0,1,2],[0,2,3],[1,2,1],[1,3,4],[2,3,3]]

Output: 3

Explanation: The shortest time from intersection 0 to intersection 3 is 6 minutes. There are 3 routes:

  1. 0 → 1 → 3 (time 2 + 4 = 6)
  2. 0 → 2 → 3 (time 3 + 3 = 6)
  3. 0 → 1 → 2 → 3 (time 2 + 1 + 3 = 6)

The route 0 → 2 → 1 → 3 takes 3 + 1 + 4 = 8 minutes, which is longer than 6, so it does not count.

Example 3

Input: n = 2, roads = [[1,0,10]]

Output: 1

Explanation: There is only one road between intersection 0 and intersection 1 (which is n-1 = 1). The only path takes 10 minutes. There is exactly 1 way.

Constraints

  • 1 ≤ n ≤ 200
  • n - 1 ≤ roads.length ≤ n × (n - 1) / 2
  • roads[i].length == 3
  • 0 ≤ u_i, v_i ≤ n - 1
  • 1 ≤ time_i ≤ 10^9
  • u_i ≠ v_i
  • There is at most one road connecting any two intersections
  • You can reach any intersection from any other intersection

Editorial

Brute Force

Intuition

The most straightforward approach is to enumerate every possible path from intersection 0 to intersection n-1. For each complete path, compute its total travel time. Then identify the minimum travel time among all paths and count how many paths achieve that minimum.

Think of it like a road trip planner that tests every conceivable route between two cities — taking every fork in the road, measuring each route's total drive time, and finally reporting how many routes tie for the fastest. We use DFS with backtracking: at each intersection, we try visiting every unvisited neighbor, recurse, then backtrack (unmark it) so other routes can use that intersection.

To avoid wasting time on routes that are already longer than the best known, we prune any path whose accumulated distance exceeds the current shortest distance.

Step-by-Step Explanation

Let's trace DFS on Example 2: n = 4, roads = [[0,1,2],[0,2,3],[1,2,1],[1,3,4],[2,3,3]]:

Initialize: min_dist = ∞, count = 0, visited = {0}.

Step 1: At node 0 (dist=0). First neighbor: node 1 (weight 2). Visit node 1.

Step 2: At node 1 (dist=2). First neighbor: node 2 (weight 1). Visit node 2.

Step 3: At node 2 (dist=3). Neighbor: node 3 (weight 3). dist = 3+3 = 6. Node 3 is destination!

  • 6 < ∞ → update min_dist = 6, count = 1. Backtrack from node 3.

Step 4: Back at node 2. Remaining neighbor node 0 is visited. Backtrack to node 1.

Step 5: At node 1 (dist=2). Next neighbor: node 3 (weight 4). dist = 2+4 = 6. Destination!

  • 6 == min_dist → increment count = 2. Backtrack.

Step 6: All neighbors of node 1 explored. Backtrack to node 0.

Step 7: At node 0 (dist=0). Next neighbor: node 2 (weight 3). Visit node 2.

Step 8: At node 2 (dist=3). Neighbor: node 1 (weight 1). Visit node 1. dist = 3+1 = 4.

Step 9: At node 1 (dist=4). Neighbor: node 3 (weight 4). dist = 4+4 = 8.

  • 8 > min_dist (6) → prune! This path is already too long. Backtrack.

Step 10: Back at node 2 (dist=3). Neighbor: node 3 (weight 3). dist = 3+3 = 6. Destination!

  • 6 == min_dist → count = 3. Backtrack.

Step 11: All paths explored. Return count = 3.

DFS explored 4 paths total (one was pruned). Even with pruning, this approach can explore exponentially many paths in dense graphs.

Algorithm

  1. Build an adjacency list from the roads.
  2. Initialize min_dist = ∞ and count = 0.
  3. Mark node 0 as visited and run DFS from node 0 with accumulated distance 0.
  4. In DFS(node, dist):
    a. If dist > min_dist, prune (return immediately).
    b. If node is the destination:
    • If dist < min_dist: set min_dist = dist, count = 1.
    • Else if dist == min_dist: count = (count + 1) mod (10^9 + 7).
    • Return.
      c. For each unvisited neighbor with edge weight w:
    • Mark neighbor visited.
    • Recurse with DFS(neighbor, dist + w).
    • Unmark neighbor (backtrack).
  5. Return count.

Code

class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        const int MOD = 1e9 + 7;
        vector<vector<pair<int, long long>>> graph(n);
        for (auto& r : roads) {
            graph[r[0]].push_back({r[1], (long long)r[2]});
            graph[r[1]].push_back({r[0], (long long)r[2]});
        }

        long long shortestDist = LLONG_MAX;
        long long count = 0;
        vector<bool> visited(n, false);
        visited[0] = true;

        function<void(int, long long)> dfs = [&](int node, long long dist) {
            if (dist > shortestDist) return;
            if (node == n - 1) {
                if (dist < shortestDist) {
                    shortestDist = dist;
                    count = 1;
                } else if (dist == shortestDist) {
                    count = (count + 1) % MOD;
                }
                return;
            }
            for (auto& [next, w] : graph[node]) {
                if (!visited[next]) {
                    visited[next] = true;
                    dfs(next, dist + w);
                    visited[next] = false;
                }
            }
        };

        dfs(0, 0);
        return (int)count;
    }
};
class Solution:
    def countPaths(self, n: int, roads: list[list[int]]) -> int:
        MOD = 10**9 + 7
        graph = [[] for _ in range(n)]
        for u, v, t in roads:
            graph[u].append((v, t))
            graph[v].append((u, t))

        shortest_dist = [float('inf')]
        count = [0]
        visited = [False] * n
        visited[0] = True

        def dfs(node, dist):
            if dist > shortest_dist[0]:
                return
            if node == n - 1:
                if dist < shortest_dist[0]:
                    shortest_dist[0] = dist
                    count[0] = 1
                elif dist == shortest_dist[0]:
                    count[0] = (count[0] + 1) % MOD
                return
            for next_node, weight in graph[node]:
                if not visited[next_node]:
                    visited[next_node] = True
                    dfs(next_node, dist + weight)
                    visited[next_node] = False

        dfs(0, 0)
        return count[0]
class Solution {
    private static final int MOD = 1_000_000_007;
    private long shortestDist = Long.MAX_VALUE;
    private int count = 0;

    public int countPaths(int n, int[][] roads) {
        List<List<long[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] r : roads) {
            graph.get(r[0]).add(new long[]{r[1], r[2]});
            graph.get(r[1]).add(new long[]{r[0], r[2]});
        }

        boolean[] visited = new boolean[n];
        visited[0] = true;
        dfs(graph, visited, 0, n - 1, 0);
        return count;
    }

    private void dfs(List<List<long[]>> graph, boolean[] visited,
                     int node, int dest, long dist) {
        if (dist > shortestDist) return;
        if (node == dest) {
            if (dist < shortestDist) {
                shortestDist = dist;
                count = 1;
            } else if (dist == shortestDist) {
                count = (int)((count + 1L) % MOD);
            }
            return;
        }
        for (long[] edge : graph.get(node)) {
            int next = (int) edge[0];
            long weight = edge[1];
            if (!visited[next]) {
                visited[next] = true;
                dfs(graph, visited, next, dest, dist + weight);
                visited[next] = false;
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n!)

In the worst case (a complete graph where all edges have equal weight), DFS explores every permutation of the n nodes as a potential path. The number of simple paths from one node to another in a complete graph is on the order of n!, making this approach infeasible for large inputs. Even with distance-based pruning, the worst case remains exponential.

Space Complexity: O(n + E)

The adjacency list takes O(n + E) space where E is the number of edges. The visited array and recursion stack each take O(n). Combined: O(n + E).

Why This Approach Is Not Efficient

The brute force DFS enumerates all possible paths, which can grow factorially with n. For n = 200 (the constraint limit), a dense graph could have millions of edges, and the number of simple paths becomes astronomical.

The core inefficiency is redundant work: DFS may compute the shortest distance to the same node many times via different routes. It does not remember that it already found the optimal distance to an intermediate node, so it explores suboptimal continuations unnecessarily.

Key Insight: We need an algorithm that:

  1. Computes shortest distances once per node (not per path).
  2. Simultaneously counts how many routes achieve each shortest distance.

Dijkstra's algorithm solves the shortest-distance problem in O((V + E) log V) time. With a small modification — maintaining a ways[] array alongside the dist[] array — we can count shortest paths at virtually no extra cost. When we find a shorter path to a node, we reset its count. When we find an equally short path, we add the incoming count. This is the optimal approach.

Optimal Approach - Modified Dijkstra's Algorithm

Intuition

Dijkstra's algorithm finds the shortest distance from a source to all other nodes in a weighted graph with non-negative edge weights. It works by always processing the unvisited node with the smallest known distance, then relaxing its outgoing edges.

The clever twist here is to augment Dijkstra's with a second array, ways[], that counts how many shortest paths reach each node. We initialize ways[0] = 1 (one way to be at the start) and ways[i] = 0 for all other nodes.

When we relax an edge from node u to node v with weight w, two things can happen:

  1. We found a shorter path: dist[u] + w < dist[v]. Update dist[v] and set ways[v] = ways[u] — all previous paths to v are no longer shortest, so we replace the count entirely.

  2. We found an equally short path: dist[u] + w == dist[v]. The distance stays the same, but we discovered additional shortest routes. Add: ways[v] += ways[u].

By the time Dijkstra finishes, ways[n-1] holds the total number of shortest paths from node 0 to the destination, which is exactly what we need.

Step-by-Step Explanation

Let's trace modified Dijkstra's on Example 2: n = 4, roads = [[0,1,2],[0,2,3],[1,2,1],[1,3,4],[2,3,3]]:

Step 1: Initialize. dist = [0, ∞, ∞, ∞], ways = [1, 0, 0, 0]. Push (0, node 0) into min-heap.

Step 2: Extract minimum: node 0 (dist 0). Examine its edges.

Step 3: Relax edge 0→1 (weight 2). New dist = 0+2 = 2 < ∞. Shorter!

  • Update dist[1] = 2, ways[1] = ways[0] = 1.

Step 4: Relax edge 0→2 (weight 3). New dist = 0+3 = 3 < ∞. Shorter!

  • Update dist[2] = 3, ways[2] = ways[0] = 1.

Step 5: Extract minimum: node 1 (dist 2). Examine its edges.

Step 6: Relax edge 1→2 (weight 1). New dist = 2+1 = 3 == dist[2] = 3. Equal!

  • Don't change dist[2]. Instead ADD ways: ways[2] = 1 + 1 = 2.
  • Two shortest paths to node 2: direct 0→2 and via 0→1→2.

Step 7: Relax edge 1→3 (weight 4). New dist = 2+4 = 6 < ∞. Shorter!

  • Update dist[3] = 6, ways[3] = ways[1] = 1.

Step 8: Extract minimum: node 2 (dist 3). Examine its edges.

Step 9: Relax edge 2→3 (weight 3). New dist = 3+3 = 6 == dist[3] = 6. Equal!

  • Don't change dist[3]. ADD ways: ways[3] = 1 + 2 = 3.
  • Three paths to node 3: 0→1→3, 0→2→3, 0→1→2→3.

Step 10: Extract minimum: node 3 (dist 6). This is the destination.

Result: ways[3] = 3. Return 3.

Modified Dijkstra's — Shortest Distance + Path Counting — Watch how Dijkstra's algorithm simultaneously finds shortest distances and counts the number of shortest paths by updating the ways array when equal-distance routes are discovered.

Algorithm

  1. Build an adjacency list from the roads.
  2. Initialize dist[i] = ∞ for all nodes, except dist[0] = 0. Initialize ways[i] = 0 for all nodes, except ways[0] = 1.
  3. Push (0, node 0) into a min-heap (priority queue).
  4. While the heap is not empty:
    a. Extract the node u with minimum distance d.
    b. If d > dist[u], skip (stale entry).
    c. For each neighbor v with edge weight w:
    • If dist[u] + w < dist[v]: found a shorter path. Set dist[v] = dist[u] + w, ways[v] = ways[u]. Push (dist[v], v) to heap.
    • Else if dist[u] + w == dist[v]: found an equally short path. Set ways[v] = (ways[v] + ways[u]) % (10^9 + 7).
  5. Return ways[n - 1].

Code

class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        const int MOD = 1e9 + 7;
        vector<vector<pair<int, long long>>> graph(n);
        for (auto& r : roads) {
            graph[r[0]].push_back({r[1], (long long)r[2]});
            graph[r[1]].push_back({r[0], (long long)r[2]});
        }

        vector<long long> dist(n, LLONG_MAX);
        vector<long long> 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] : graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    ways[v] = ways[u];
                    pq.push({dist[v], v});
                } else if (dist[u] + w == dist[v]) {
                    ways[v] = (ways[v] + ways[u]) % MOD;
                }
            }
        }
        return (int)ways[n - 1];
    }
};
import heapq

class Solution:
    def countPaths(self, n: int, roads: list[list[int]]) -> int:
        MOD = 10**9 + 7
        graph = [[] for _ in range(n)]
        for u, v, t in roads:
            graph[u].append((v, t))
            graph[v].append((u, t))

        dist = [float('inf')] * n
        ways = [0] * n
        dist[0] = 0
        ways[0] = 1

        pq = [(0, 0)]

        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    ways[v] = ways[u]
                    heapq.heappush(pq, (dist[v], v))
                elif dist[u] + w == dist[v]:
                    ways[v] = (ways[v] + ways[u]) % MOD

        return ways[n - 1]
class Solution {
    public int countPaths(int n, int[][] roads) {
        final int MOD = 1_000_000_007;
        List<List<long[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] r : roads) {
            graph.get(r[0]).add(new long[]{r[1], r[2]});
            graph.get(r[1]).add(new long[]{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[] curr = pq.poll();
            long d = curr[0];
            int u = (int) curr[1];
            if (d > dist[u]) continue;
            for (long[] edge : graph.get(u)) {
                int v = (int) edge[0];
                long w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    ways[v] = ways[u];
                    pq.offer(new long[]{dist[v], v});
                } else if (dist[u] + w == dist[v]) {
                    ways[v] = (ways[v] + ways[u]) % MOD;
                }
            }
        }
        return (int) ways[n - 1];
    }
}

Complexity Analysis

Time Complexity: O((V + E) log V)

Dijkstra's algorithm with a min-heap processes each node once and each edge at most once. Each heap insertion and extraction takes O(log V). With V nodes and E edges, the total time is O((V + E) log V). For this problem, V = n ≤ 200 and E ≤ n(n-1)/2 ≤ 19900, so the algorithm runs in well under a millisecond.

The path counting logic (updating ways[]) adds only O(1) work per edge relaxation, so it does not affect the asymptotic complexity.

Space Complexity: O(V + E)

The adjacency list takes O(V + E). The dist[] and ways[] arrays each take O(V). The priority queue can hold at most O(E) entries in the worst case. Combined: O(V + E).