Problem Statement
You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.
You are given an integer n and a 2D integer array roads where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know in how many ways you can travel from intersection 0 to intersection n – 1 in the shortest amount of time.
Return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo 109 + 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: The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes. The four ways to get there in 7 minutes are:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
Example 2:
Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation:There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.
Constraints
1 <= n <= 200n - 1 <= roads.length <= n * (n - 1) / 2roads[i].length == 30 <= ui, vi <= n - 11 <= timei <= 109ui != vi- There is at most one road connecting any two intersections.
- You can reach any intersection from any other intersection.
Approach
- Build an
adjacency listfrom the given roads. - Use Dijkstra’s algorithm to find the shortest distance from node 0 to all nodes.
- Along with distance
(minW), maintainpathCount[i]= number of shortest paths to node i. - Initialize:
minW[0] = 0, pathCount[0] = 1Min-heap (priority queue) with[0, 0]
- For each extracted node:
- If a
shorter pathto a neighbor is found, update its distance and copy the path count. - If an
equal shortest pathis found, add the path count (mod 109 + 7).
- If a
- Final answer is
pathCount[n-1], the number of shortest paths to the destination.
Time & Space Complexity
Time Complexity: O((V + E) log V)
Here, V = n (number of nodes), E = roads.length
Space Complexity: O(V + E)
Dry Run
Input: n = 3,
roads = [[0,1,1],[1,2,1],[0,2,2]]
Step 0: Start Function countPaths(3, roads)
Step 1: Build Graph (Adjacency List) graph = [ [[1, 1], [2, 2]], [[0, 1], [2, 1]], [[1, 1], [0, 2]] ] Step 2: Initialize Variables minW = [Infinity, Infinity, Infinity] pathCount = [0, 0, 0] Priority Queue (pq): pq = [[0, 0]] minW[0] = 0 pathCount[0] = 1 Step 3: First Pop from Priority Queue [currW, curr] = [0, 0] Step 4: Explore Neighbors of Node 0 Neighbor = 1 Edge Weight = 1 newW = 0 + 1 = 1 1 < Infinity → update shortest path minW = [0, 1, Infinity] pathCount = [1, 1, 0] pq.push([1, 1]) Neighbor = 2 Edge Weight = 2 newW = 0 + 2 = 2 2 < Infinity → update shortest path minW = [0, 1, 2] pathCount = [1, 1, 1] pq.push([2, 2]) Step 5: Second Pop from Priority Queue [currW, curr] = [1, 1] Step 6: Explore Neighbors of Node 1 Neighbor = 0 Edge Weight = 1 newW = 1 + 1 = 2 2 > minW[0] → ignore this path Neighbor = 2 Edge Weight = 1 newW = 1 + 1 = 2 newW == minW[2] Alternate shortest path found pathCount[2] = pathCount[1] + pathCount[2] pathCount[2] = 1 + 1 = 2 Step 7: Third Pop from Priority Queue [currW, curr] = [2, 2] Step 8: Explore Neighbors of Node 2 Neighbor = 1 Edge Weight = 1 newW = 2 + 1 = 3 3 > minW[1] → ignore Neighbor = 0 Edge Weight = 2 newW = 2 + 2 = 4 4 > minW[0] → ignore Step 9: End of Dijkstra Loop Priority Queue is empty Step 10: Final State minW = [0, 1, 2] pathCount = [1, 1, 2]
Step 11: Return Result pathCount[n - 1] = pathCount[2] = 2
Output: 2
var countPaths = function(n, roads) {
//create adj list
let graph = Array.from({ length: n }, () => []);
for(let [u, v, w] of roads) {
graph[u].push([v, w]);
graph[v].push([u, w]);
}
// PQ, minWeight, pathCount
let pq = new MinPriorityQueue(x => x[0]);
let minW = new Array(n).fill(Infinity);
let pathCount = new Array(n).fill(0);
pq.push([0, 0]);
minW[0] = 0;
pathCount[0] = 1;
// Dijkstra's Algorithm
while(!pq.isEmpty()) {
let [currW, curr] = pq.pop();
for(let [neighbor, neighborW] of graph[curr]) {
let newW = currW + neighborW;
// new shortest path
if(newW < minW[neighbor]) {
minW[neighbor] = newW
pq.push([newW, neighbor]);
pathCount[neighbor] = pathCount[curr];
}
// alternative shortest path
else if(newW === minW[neighbor]) {
pathCount[neighbor] = (pathCount[curr] + pathCount[neighbor]) % (1e9 + 7);
}
}
}
return pathCount[(n-1)];
};
import heapq
def countPaths(n, roads):
MOD = 10**9 + 7
graph = [[] for _ in range(n)]
for u, v, w in roads:
graph[u].append((v, w))
graph[v].append((u, w))
minW = [float('inf')] * n
pathCount = [0] * n
minW[0] = 0
pathCount[0] = 1
pq = [(0, 0)] # (weight, node)
while pq:
currW, curr = heapq.heappop(pq)
if currW > minW[curr]:
continue
for neighbor, w in graph[curr]:
newW = currW + w
if newW < minW[neighbor]:
minW[neighbor] = newW
pathCount[neighbor] = pathCount[curr]
heapq.heappush(pq, (newW, neighbor))
elif newW == minW[neighbor]:
pathCount[neighbor] = (pathCount[neighbor] + pathCount[curr]) % MOD
return pathCount[n - 1]
import java.util.*;
class Solution {
static final int MOD = 1000000007;
public int countPaths(int n, int[][] roads) {
List> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int[] r : roads) {
graph.get(r[0]).add(new int[]{r[1], r[2]});
graph.get(r[1]).add(new int[]{r[0], r[2]});
}
long[] minW = new long[n];
long[] pathCount = new long[n];
Arrays.fill(minW, Long.MAX_VALUE);
minW[0] = 0;
pathCount[0] = 1;
PriorityQueue pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
pq.offer(new long[]{0, 0});
while (!pq.isEmpty()) {
long[] curr = pq.poll();
long currW = curr[0];
int node = (int) curr[1];
if (currW > minW[node]) continue;
for (int[] nei : graph.get(node)) {
int next = nei[0];
long newW = currW + nei[1];
if (newW < minW[next]) {
minW[next] = newW;
pathCount[next] = pathCount[node];
pq.offer(new long[]{newW, next});
} else if (newW == minW[next]) {
pathCount[next] = (pathCount[next] + pathCount[node]) % MOD;
}
}
}
return (int) pathCount[n - 1];
}
}
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int countPaths(int n, vector>& roads) {
const int MOD = 1e9 + 7;
vector>> graph(n);
for (auto &r : roads) {
graph[r[0]].push_back({r[1], r[2]});
graph[r[1]].push_back({r[0], r[2]});
}
vector minW(n, LLONG_MAX), pathCount(n, 0);
minW[0] = 0;
pathCount[0] = 1;
priority_queue, vector>, greater<>> pq;
pq.push({0, 0});
while (!pq.empty()) {
auto [currW, curr] = pq.top();
pq.pop();
if (currW > minW[curr]) continue;
for (auto &[next, w] : graph[curr]) {
long long newW = currW + w;
if (newW < minW[next]) {
minW[next] = newW;
pathCount[next] = pathCount[curr];
pq.push({newW, next});
} else if (newW == minW[next]) {
pathCount[next] = (pathCount[next] + pathCount[curr]) % MOD;
}
}
}
return pathCount[n - 1];
}
};
#include <stdio.h>
#include <limits.h>
#define MAXN 200
#define MOD 1000000007
long long minW[MAXN], pathCount[MAXN];
int graph[MAXN][MAXN], weight[MAXN][MAXN];
int minNode(int n, int visited[]) {
long long min = LLONG_MAX;
int idx = -1;
for (int i = 0; i < n; i++) {
if (!visited[i] && minW[i] < min) {
min = minW[i];
idx = i;
}
}
return idx;
}
int countPaths(int n) {
int visited[MAXN] = {0};
for (int i = 0; i < n; i++) {
minW[i] = LLONG_MAX;
pathCount[i] = 0;
}
minW[0] = 0;
pathCount[0] = 1;
for (int i = 0; i < n; i++) {
int u = minNode(n, visited);
if (u == -1) break;
visited[u] = 1;
for (int v = 0; v < n; v++) {
if (graph[u][v]) {
long long newW = minW[u] + weight[u][v];
if (newW < minW[v]) {
minW[v] = newW;
pathCount[v] = pathCount[u];
} else if (newW == minW[v]) {
pathCount[v] = (pathCount[v] + pathCount[u]) % MOD;
}
}
}
}
return pathCount[n - 1];
}
using System;
using System.Collections.Generic;
public class Solution {
const int MOD = 1000000007;
public int CountPaths(int n, int[][] roads) {
var graph = new List<(int, int)>[n];
for (int i = 0; i < n; i++) graph[i] = new List<(int, int)>();
foreach (var r in roads) {
graph[r[0]].Add((r[1], r[2]));
graph[r[1]].Add((r[0], r[2]));
}
long[] minW = new long[n];
long[] pathCount = new long[n];
Array.Fill(minW, long.MaxValue);
minW[0] = 0;
pathCount[0] = 1;
var pq = new PriorityQueue<(int node, long dist), long>();
pq.Enqueue((0, 0), 0);
while (pq.Count > 0) {
var (curr, currW) = pq.Dequeue();
if (currW > minW[curr]) continue;
foreach (var (next, w) in graph[curr]) {
long newW = currW + w;
if (newW < minW[next]) {
minW[next] = newW;
pathCount[next] = pathCount[curr];
pq.Enqueue((next, newW), newW);
} else if (newW == minW[next]) {
pathCount[next] = (pathCount[next] + pathCount[curr]) % MOD;
}
}
}
return (int) pathCount[n - 1];
}
}
