LeetCode 1786. 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 <= 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(zi) > 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

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 <= ui, vi <= n

• ui != vi

• 1 <= weighti <= 10^5

• There is at most one edge between any two nodes.

• There is at least one path between any two nodes.

Solution:

English Version in Youtube

中文版解答Youtube Link

中文版解答Bilibili Link

class Solution {
public:
    
    void bfs(int n, const vector<vector<pair<int, int>>>& graph, vector<int>& distances, vector<int>& closest_nodes) {
        auto cmp = [](const pair<int, int> &a, const pair<int, int> &b) {
            return a.second > b.second;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        vector<bool> visited(n+1, false);
        pq.push({n, 0});
        
        while (!pq.empty()) {
            pair<int, int> current = pq.top();
            pq.pop();
            int node = current.first;
            int dis = current.second;
            if (visited[node] == true) {
                continue;
            }
            distances[node] = dis;
            visited[node] = true;
            closest_nodes.push_back(node);
            
            for (pair<int, int> neighbor : graph[node]) {
                int neighbor_node = neighbor.first;
                if (visited[neighbor_node] == false) {
                    pq.push({neighbor_node, dis + neighbor.second});
                }
            }
        }
    }
    
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int, int>>> graph(n+1);
        for (const vector<int>& edge : edges) {
            graph[edge[0]].push_back({edge[1], edge[2]});
            graph[edge[1]].push_back({edge[0], edge[2]});
        }
        
        vector<int> distances(n + 1, 0);
        vector<int> closest_nodes;
        bfs(n, graph, distances, closest_nodes);
        
        vector<long> dp(n+1, 0);
        dp[1] = 1;
        int mod = 1e9+7;
        for (int i = closest_nodes.size() - 1; i >= 0; i--) {
            int node = closest_nodes[i];
            for (pair<int, int> neighbor : graph[node]) {
                int neighbor_node = neighbor.first;
                if (distances[neighbor_node] < distances[node]) {
                    dp[neighbor_node] += dp[node];
                    dp[neighbor_node] %= mod;
                }
            }
        }
        
        return dp[n];
    }
};