1976. Number of Ways to Arrive at Destination LeetCode Solution
In this guide, you will get 1976. Number of Ways to Arrive at Destination LeetCode Solution with the best time and space complexity. The solution to Number of Ways to Arrive at Destination problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Ways to Arrive at Destination
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.
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 <= 200
n – 1 <= roads.length <= n * (n – 1) / 2
roads[i].length == 3
0 <= ui, vi <= n – 1
1 <= timei <= 109
ui != vi
There is at most one road connecting any two intersections.
You can reach any intersection from any other intersection.
Complexity Analysis
Time Complexity: O((|V| + |E|)\log |V|)
Space Complexity: O(|E| + |V|)
1976. Number of Ways to Arrive at Destination LeetCode Solution in C++
class Solution {
public:
int countPaths(int n, vector<vector<int>>& roads) {
vector<vector<pair<int, int>>> graph(n);
for (const vector<int>& road : roads) {
const int u = road[0];
const int v = road[1];
const int w = road[2];
graph[u].emplace_back(v, w);
graph[v].emplace_back(u, w);
}
return dijkstra(graph, 0, n - 1);
}
private:
// Similar to 1786. Number of Restricted Paths From First to Last Node
int dijkstra(const vector<vector<pair<int, int>>>& graph, int src, int dst) {
constexpr int kMod = 1'000'000'007;
vector<long> ways(graph.size());
vector<long> dist(graph.size(), LONG_MAX);
ways[src] = 1;
dist[src] = 0;
using P = pair<long, int>; // (d, u)
priority_queue<P, vector<P>, greater<>> minHeap;
minHeap.emplace(dist[src], src);
while (!minHeap.empty()) {
const auto [d, u] = minHeap.top();
minHeap.pop();
if (d > dist[u])
continue;
for (const auto& [v, w] : graph[u])
if (d + w < dist[v]) {
dist[v] = d + w;
ways[v] = ways[u];
minHeap.emplace(dist[v], v);
} else if (d + w == dist[v]) {
ways[v] += ways[u];
ways[v] %= kMod;
}
}
return ways[dst];
}
}; /* code provided by PROGIEZ */
1976. Number of Ways to Arrive at Destination LeetCode Solution in Java
class Solution {
public int countPaths(int n, int[][] roads) {
List<Pair<Integer, Integer>>[] graph = new List[n];
for (int i = 0; i < n; i++)
graph[i] = new ArrayList<>();
for (int[] road : roads) {
final int u = road[0];
final int v = road[1];
final int w = road[2];
graph[u].add(new Pair<>(v, w));
graph[v].add(new Pair<>(u, w));
}
return dijkstra(graph, 0, n - 1);
}
private int dijkstra(List<Pair<Integer, Integer>>[] graph, int src, int dst) {
final int kMod = 1_000_000_007;
long[] ways = new long[graph.length];
Arrays.fill(ways, 0);
long[] dist = new long[graph.length];
Arrays.fill(dist, Long.MAX_VALUE);
ways[src] = 1;
dist[src] = 0;
Queue<Pair<Long, Integer>> minHeap = new PriorityQueue<>(Comparator.comparing(Pair::getKey)) {
{ offer(new Pair<>(dist[src], src)); }
};
while (!minHeap.isEmpty()) {
final long d = minHeap.peek().getKey();
final int u = minHeap.poll().getValue();
if (d > dist[u])
continue;
for (Pair<Integer, Integer> pair : graph[u]) {
final int v = pair.getKey();
final int w = pair.getValue();
if (d + w < dist[v]) {
dist[v] = d + w;
ways[v] = ways[u];
minHeap.offer(new Pair<>(dist[v], v));
} else if (d + w == dist[v]) {
ways[v] += ways[u];
ways[v] %= kMod;
}
}
}
return (int) ways[dst];
}
} // code provided by PROGIEZ
1976. Number of Ways to Arrive at Destination LeetCode Solution in Python
class Solution:
def countPaths(self, n: int, roads: list[list[int]]) -> int:
graph = [[] for _ in range(n)]
for u, v, w in roads:
graph[u].append((v, w))
graph[v].append((u, w))
return self._dijkstra(graph, 0, n - 1)
def _dijkstra(
self,
graph: list[list[tuple[int, int]]],
src: int,
dst: int,
) -> int:
kMod = 10**9 + 7
ways = [0] * len(graph)
dist = [math.inf] * len(graph)
ways[src] = 1
dist[src] = 0
minHeap = [(dist[src], src)]
while minHeap:
d, u = heapq.heappop(minHeap)
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]:
dist[v] = d + w
ways[v] = ways[u]
heapq.heappush(minHeap, (dist[v], v))
elif d + w == dist[v]:
ways[v] += ways[u]
ways[v] %= kMod
return ways[dst] # code by PROGIEZ
