A city contains n intersections numbered from 0 to n - 1. Each road [u, v, time] connects intersections u and v in both directions and requires the stated travel time.
The road network is connected, meaning every intersection can be reached from every other intersection.
Return the number of distinct routes from intersection 0 to intersection n - 1 having minimum total travel time. Return the count 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: Four routes take the minimum time 7: 0->6, 0->4->6, 0->1->2->5->6, and 0->1->3->5->6.
Example 2
Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: The only route from intersection 0 to intersection 1 has travel time 10.
Approach
Dijkstra’s Algorithm processes intersections in increasing shortest travel time. A distance array stores the minimum travel time to every intersection, while a ways array stores the number of routes achieving the corresponding minimum.
A strictly shorter route replaces both the distance and route count because previous routes become non-optimal. An equally short route preserves the distance and adds another group of shortest routes.
Algorithm
Build an undirected weighted adjacency list by storing every road in both directions with the corresponding travel time.
Initialize all distances as infinity and all route counts as
0; setdist[0]=0,ways[0]=1, and insert{0, 0}into a min-heap.Continue processing while the heap contains entries and remove the intersection having the smallest travel time.
Skip the removed entry when the heap time differs from the current stored distance, as the entry represents an outdated route.
Traverse every adjacent road and calculate the candidate time as
currentTime+roadTime.For a strictly shorter candidate, replace the neighbor distance, copy
ways[current]intoways[neighbor], and insert the updated pair into the heap.For an equal candidate, add
ways[current]toways[neighbor]modulo10^9+7; returnways[N-1]after heap processing finishes.
Dry Run
number-of-ways-fully-corrected-edge-2-3
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Return the number of shortest routes from 0 to n - 1. int countPaths(int n, vector<vector<int>>& roads) { const int MOD = 1000000007; vector<vector<pair<int, int>>> adj(n); // Build an undirected weighted adjacency list. for (const vector<int>& road : roads) { int u = road[0]; int v = road[1]; int travelTime = road[2]; adj[u].push_back({v, travelTime}); adj[v].push_back({u, travelTime}); } const long long INF = numeric_limits<long long>::max() / 4; vector<long long> dist(n, INF); vector<int> ways(n, 0); priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> minHeap; // Initialize source distance and route count. dist[0] = 0; ways[0] = 1; minHeap.push({0, 0}); // Process intersections by smallest known travel time. while (!minHeap.empty()) { auto [currentDistance, node] = minHeap.top(); minHeap.pop(); // Skip an entry replaced by a shorter route. if (currentDistance != dist[node]) { continue; } // Relax every road leaving the selected intersection. for (const auto& [neighbor, travelTime] : adj[node]) { long long candidate = currentDistance + travelTime; // Replace distance and inherit every shortest route. if (candidate < dist[neighbor]) { dist[neighbor] = candidate; ways[neighbor] = ways[node]; minHeap.push({candidate, neighbor}); } // Add another group of equally short routes. else if (candidate == dist[neighbor]) { ways[neighbor] = (ways[neighbor] + ways[node]) % MOD; } } } return ways[n - 1]; }};// Driver code.int main() { int n = 7; vector<vector<int>> 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} }; Solution sol; cout << sol.countPaths(n, roads); return 0;}Complexity Analysis
Time Complexity: O((N+M)×log N), where N is the number of intersections and M is the number of roads; heap operations process extractions and successful relaxations.
Space Complexity: O(N+M), where the adjacency list stores N intersections and 2M road entries, while the distance, ways, and heap storage require O(N+M) space.
Interview follow-up Questions
Every previously counted route has a larger travel time, so only routes reaching the new minimum remain valid.
Be the first to add a comment.