LeetCode 1786. 从第一个节点出发到最后一个节点的受限路径数（迪杰斯特拉 + 拓扑排序）

输入：n = 5, 
edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
输出：3
解释：每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。
三条受限路径分别是：
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5
3) 1 --> 3 --> 5

输入：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]]
输出：1
解释：每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。
唯一一条受限路径是：1 --> 3 --> 7 。
 
提示：
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
任意两个节点之间至多存在一条边
任意两个节点之间至少存在一条路径

typedef pair<int, int> pii;
struct cmp{
    bool operator()(pii& a, pii& b) const
    {
        return a.first > b.first;
    }
};
class Solution {
public:
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        // 建图，迪杰斯特拉 求解 每个节点到 n 的最短距离 dis
        vector<unordered_map<int,int>> g(n);
        for(auto & e : edges)
        {
            g[e[0]-1][e[1]-1] = e[2];
            g[e[1]-1][e[0]-1] = e[2];
        }
        vector<int> dis(n, INT_MAX);
        priority_queue<pii, vector<pii>, cmp> q;
        dis[n-1] = 0;
        q.push({0, n-1});
        while(!q.empty())
        {
            pii tp = q.top();
            int d = tp.first;
            int id = tp.second;
            q.pop();
            for(auto it = g[id].begin(); it != g[id].end(); ++it)
            {
                int nid = it->first;
                int nd = it->second;
                if(d + nd < dis[nid])
                {
                    dis[nid] = d + nd;
                    q.push({dis[nid], nid});
                }
            }
        }

        // 建立 从 1 节点开始的 dis 递减图，并记录入度
        vector<int> indegree(n, 0);
        unordered_map<int,unordered_set<int>> g2;
        queue<int> q1;
        q1.push(0);
        unordered_set<int> vis;
        vis.insert(0);
        while(!q1.empty())
        {
            int id = q1.front();
            q1.pop();
            for(auto it = g[id].begin(); it != g[id].end(); ++it)
            {
                int nid = it->first;
                if(dis[id] > dis[nid])//递减
                {
                    g2[id].insert(nid);//建图
                    indegree[nid]++;//记录出入度
                    if(!vis.count(nid))//防止重复记录入度
                    {
                        vis.insert(nid);
                        q1.push(nid);
                    }
                }
            }
        }
        // 拓扑排序
        long long mod = 1e9+7;
        vector<long long> ans(n, 0);
        ans[0] = 1;
        queue<int> q2;
        q2.push(0);
        while(!q2.empty())
        {
            int id = q2.front();
            q2.pop();
            for(auto it = g2[id].begin(); it != g2[id].end(); ++it)
            {
                int nid = *it;
                ans[nid] = (ans[nid] + ans[id])%mod;
                if(--indegree[nid] == 0)
                    q2.push(nid);
            }
        }
        return ans[n-1]%mod;
    }
};