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

1786. Number of Restricted Paths From First to Last Node

Level

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:

Image text

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:

Image text

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[]>());
            list1.add(new int[]{v, weight});
            list2.add(new int[]{u, weight});
            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];
            g[u].add(new int[] {v, w});
            g[v].add(new int[] {u, w});
        }
        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)
}

1786 - Number of Restricted Paths From First to Last Node

1786. Number of Restricted Paths From First to Last Node

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1786. Number of Restricted Paths From First to Last Node

Level

Description

Solution

All Problems

All Solutions