Formatted question description: https://leetcode.ca/all/1786.html

1786. Number of Restricted Paths From First to Last Node

Medium

Description

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] = [u_i, v_i, weight_i] denotes that there is an edge between nodes u_i and v_i with weight equal to weight_i.

A path from node start to node end is a sequence of nodes [z_0, z_1, z_2, ..., z_k] such that z_0 = start and z_k = end and there is an edge between z_i and z_(i+1) where 0 <= i <= k-1.

The distance of a path is the sum of the weights on the edges of the path. Let distanceToLastNode(x) denote the shortest distance of a path between node n and node x. A restricted path is a path that also satisfies that distanceToLastNode(z_i) > distanceToLastNode(z_(i+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 10^9 + 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

Example 2:

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 * 10^4
• n - 1 <= edges.length <= 4 * 10^4
• edges[i].length == 3
• 1 <= u_i, v_i <= n
• u_i != v_i
• 1 <= weight_i <= 10^5
• There is at most one edge between any two nodes.
• There is at least one path between any two nodes.

Solution

Use a hash map to store each node’s adjacent nodes and the corresponding weights. Then use Dijkstra’s algorithm to find the shortest path from node n to each node. Finally, use dynamic programming to find the number of restricted paths that start from node 1 and end at node n.

• class Solution {
static final int MODULO = 1000000007;
int restrictedPaths = 0;
int n = 0;
int[] dp;

public int countRestrictedPaths(int n, int[][] edges) {
this.n = n;
Map<Integer, List<int[]>> map = new HashMap<Integer, List<int[]>>();
for (int[] edge : edges) {
int u = edge[0], v = edge[1], weight = edge[2];
List<int[]> list1 = map.getOrDefault(u, new ArrayList<int[]>());
List<int[]> list2 = map.getOrDefault(v, new ArrayList<int[]>());
map.put(u, list1);
map.put(v, list2);
}
int[] distances = getShortestDistances(n, map);
dp = new int[n + 1];
dp[n] = 1;
return backtrack(distances, map, 1);
}

public int[] getShortestDistances(int n, Map<Integer, List<int[]>> map) {
int[] distances = new int[n + 1];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[n] = 0;
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer node1, Integer node2) {
return distances[node1] - distances[node2];
}
});
priorityQueue.offer(n);
while (!priorityQueue.isEmpty()) {
int node = priorityQueue.poll();
int distance = distances[node];
List<int[]> list = map.getOrDefault(node, new ArrayList<int[]>());
for (int[] next : list) {
int nextNode = next[0], weight = next[1];
if (distance + weight < distances[nextNode]) {
distances[nextNode] = distance + weight;
priorityQueue.offer(nextNode);
}
}
}
return distances;
}

public int backtrack(int[] distances, Map<Integer, List<int[]>> map, int node) {
if (dp[node] == 0) {
int curDistance = distances[node];
List<int[]> list = map.getOrDefault(node, new ArrayList<int[]>());
for (int[] next : list) {
int nextNode = next[0];
if (distances[nextNode] < curDistance) {
int nextCount = backtrack(distances, map, nextNode);
dp[node] = (dp[node] + nextCount) % MODULO;
}
}
}
return dp[node];
}
}

############

class Solution {
private static final int INF = Integer.MAX_VALUE;
private static final int MOD = (int) 1e9 + 7;
private List<int[]>[] g;
private int[] dist;
private int[] f;
private int n;

public int countRestrictedPaths(int n, int[][] edges) {
this.n = n;
g = new List[n + 1];
for (int i = 0; i < g.length; ++i) {
g[i] = new ArrayList<>();
}
for (int[] e : edges) {
int u = e[0], v = e[1], w = e[2];
}
PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]);
q.offer(new int[] {0, n});
dist = new int[n + 1];
f = new int[n + 1];
Arrays.fill(dist, INF);
Arrays.fill(f, -1);
dist[n] = 0;
while (!q.isEmpty()) {
int[] p = q.poll();
int u = p[1];
for (int[] ne : g[u]) {
int v = ne[0], w = ne[1];
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
q.offer(new int[] {dist[v], v});
}
}
}
return dfs(1);
}

private int dfs(int i) {
if (f[i] != -1) {
return f[i];
}
if (i == n) {
return 1;
}
int ans = 0;
for (int[] ne : g[i]) {
int j = ne[0];
if (dist[i] > dist[j]) {
ans = (ans + dfs(j)) % MOD;
}
}
f[i] = ans;
return ans;
}
}

• // OJ: https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node/
// Time: O(ElogE)
// Space: O(E)
class Solution {
typedef pair<int, int> PII;
public:
int countRestrictedPaths(int n, vector<vector<int>>& E) {
long mod = 1e9 + 7;
vector<vector<PII>> G(n);
for (auto &e : E) {
int u = e[0] - 1, v = e[1] - 1, w = e[2];
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
priority_queue<PII, vector<PII>, greater<PII>> pq;
vector<long> dist(n, INT_MAX), cnt(n, 0);
dist[n - 1] = 0;
cnt[n - 1] = 1;
pq.emplace(0, n - 1);
while (pq.size()) {
auto [cost, u] = pq.top();
pq.pop();
if (cost > dist[u]) continue;
for (auto &[v, w] : G[u]) {
if (dist[v] > cost + w) {
dist[v] = cost + w;
pq.emplace(dist[v], v);
}
if (cost > dist[v]) cnt[u] = (cnt[u] + cnt[v]) % mod;
}
}
return cnt[0];
}
};

• class Solution:
def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
@cache
def dfs(i):
if i == n:
return 1
ans = 0
for j, _ in g[i]:
if dist[i] > dist[j]:
ans = (ans + dfs(j)) % mod
return ans

g = defaultdict(list)
for u, v, w in edges:
g[u].append((v, w))
g[v].append((u, w))
q = [(0, n)]
dist = [inf] * (n + 1)
dist[n] = 0
mod = 10**9 + 7
while q:
_, u = heappop(q)
for v, w in g[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heappush(q, (dist[v], v))
return dfs(1)


• const inf = math.MaxInt32
const mod = 1e9 + 7

type pair struct {
first  int
second int
}

var _ heap.Interface = (*pairs)(nil)

type pairs []pair

func (a pairs) Len() int { return len(a) }
func (a pairs) Less(i int, j int) bool {
return a[i].first < a[j].first || a[i].first == a[j].first && a[i].second < a[j].second
}
func (a pairs) Swap(i int, j int)   { a[i], a[j] = a[j], a[i] }
func (a *pairs) Push(x interface{}) { *a = append(*a, x.(pair)) }
func (a *pairs) Pop() interface{}   { l := len(*a); t := (*a)[l-1]; *a = (*a)[:l-1]; return t }

func countRestrictedPaths(n int, edges [][]int) int {
g := make([]pairs, n+1)
for _, e := range edges {
u, v, w := e[0], e[1], e[2]
g[u] = append(g[u], pair{v, w})
g[v] = append(g[v], pair{u, w})
}
dist := make([]int, n+1)
f := make([]int, n+1)
for i := range dist {
dist[i] = inf
f[i] = -1
}
dist[n] = 0
h := make(pairs, 0)
heap.Push(&h, pair{0, n})
for len(h) > 0 {
u := heap.Pop(&h).(pair).second
for _, ne := range g[u] {
v, w := ne.first, ne.second
if dist[v] > dist[u]+w {
dist[v] = dist[u] + w
heap.Push(&h, pair{dist[v], v})
}
}
}
var dfs func(int) int
dfs = func(i int) int {
if f[i] != -1 {
return f[i]
}
if i == n {
return 1
}
ans := 0
for _, ne := range g[i] {
j := ne.first
if dist[i] > dist[j] {
ans = (ans + dfs(j)) % mod
}
}
f[i] = ans
return ans
}
return dfs(1)
}