1786. Number of Restricted Paths From First to Last Node LeetCode Solution
In this guide, you will get 1786. Number of Restricted Paths From First to Last Node LeetCode Solution with the best time and space complexity. The solution to Number of Restricted Paths From First to Last Node 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 Restricted Paths From First to Last Node
There is an undirected weighted connected graph. You are given a positive integer n which denotes that the graph has n nodes labeled from 1 to n, and an array edges where each edges[i] = [ui, vi, weighti] denotes that there is an edge between nodes ui and vi with weight equal to weighti.
A path from node start to node end is a sequence of nodes [z0, z1, z2, …, zk] such that z0 = start and zk = end and there is an edge between zi and zi+1 where 0 <= i distanceToLastNode(zi+1) where 0 <= i <= k-1.
Return the number of restricted paths from node 1 to node n. Since that number may be too large, return it modulo 109 + 7.
Example 1:
Input: n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
Output: 3
Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The three restricted paths are:
1) 1 –> 2 –> 5
2) 1 –> 2 –> 3 –> 5
3) 1 –> 3 –> 5
Input: n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
Output: 1
Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The only restricted path is 1 –> 3 –> 7.
Constraints:
1 <= n <= 2 * 104
n – 1 <= edges.length <= 4 * 104
edges[i].length == 3
1 <= ui, vi <= n
ui != vi
1 <= weighti <= 105
There is at most one edge between any two nodes.
There is at least one path between any two nodes.
Complexity Analysis
Time Complexity: O((|V| + |E|)\log |V|)
Space Complexity: O(|E| + |V|)
1786. Number of Restricted Paths From First to Last Node LeetCode Solution in C++
class Solution {
public:
int countRestrictedPaths(int n, vector<vector<int>>& edges) {
vector<vector<pair<int, int>>> graph(n);
for (const vector<int>& edge : edges) {
const int u = edge[0] - 1;
const int v = edge[1] - 1;
const int w = edge[2];
graph[u].emplace_back(v, w);
graph[v].emplace_back(u, w);
}
return dijkstra(graph, 0, n - 1);
}
private:
int dijkstra(const vector<vector<pair<int, int>>>& graph, int src, int dst) {
constexpr int kMod = 1'000'000'007;
// ways[i] := the number of restricted path from i to n
vector<long> ways(graph.size());
// dist[i] := the distance to the last node of i
vector<long> dist(graph.size(), LONG_MAX);
ways[dst] = 1;
dist[dst] = 0;
using P = pair<long, int>; // (d, u)
priority_queue<P, vector<P>, greater<>> minHeap;
minHeap.emplace(dist[dst], dst);
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;
minHeap.emplace(dist[v], v);
}
if (dist[v] < dist[u]) {
ways[u] += ways[v];
ways[u] %= kMod;
}
}
}
return ways[src];
}
}; /* code provided by PROGIEZ */
1786. Number of Restricted Paths From First to Last Node LeetCode Solution in Java
class Solution {
public int countRestrictedPaths(int n, int[][] edges) {
List<Pair<Integer, Integer>>[] graph = new List[n];
for (int i = 0; i < n; ++i)
graph[i] = new ArrayList<>();
for (int[] edge : edges) {
final int u = edge[0] - 1;
final int v = edge[1] - 1;
final int w = edge[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;
// ways[i] := the number of restricted path from i to n
long[] ways = new long[graph.length];
// dist[i] := the distance to the last node of i
long[] dist = new long[graph.length];
Arrays.fill(dist, Long.MAX_VALUE);
ways[dst] = 1;
dist[dst] = 0;
// (d, u)
Queue<Pair<Long, Integer>> minHeap = new PriorityQueue<>(Comparator.comparing(Pair::getKey));
minHeap.offer(new Pair<>(dist[dst], dst));
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;
minHeap.offer(new Pair<>(dist[v], v));
}
if (dist[v] < dist[u]) {
ways[u] += ways[v];
ways[u] %= kMod;
}
}
}
return (int) ways[src];
}
} // code provided by PROGIEZ
1786. Number of Restricted Paths From First to Last Node LeetCode Solution in Python
class Solution:
def countRestrictedPaths(self, n: int, edges: list[list[int]]) -> int:
graph = [[] for _ in range(n)]
for u, v, w in edges:
graph[u - 1].append((v - 1, w))
graph[v - 1].append((u - 1, 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[i] := the number of restricted path from i to n
ways = [0] * len(graph)
# dist[i] := the distance to the last node of i
dist = [math.inf] * len(graph)
ways[dst] = 1
dist[dst] = 0
minHeap = [(dist[dst], dst)] # (d, u)
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
heapq.heappush(minHeap, (dist[v], v))
if dist[v] < dist[u]:
ways[u] += ways[v]
ways[u] %= kMod
return ways[src] # code by PROGIEZ
