网站建设开,水果网站建设,百度手机软件应用中心,长沙住房和建设局网站文章目录1. 题目2. 解题1. 题目
现有一个加权无向连通图。 给你一个正整数 n #xff0c;表示图中有 n 个节点#xff0c;并按从 1 到 n 给节点编号#xff1b;另给你一个数组 edges #xff0c;其中每个 edges[i] [ui, vi, weighti] 表示存在一条位于节点 ui 和 vi 之间…
文章目录1. 题目2. 解题1. 题目
现有一个加权无向连通图。 给你一个正整数 n 表示图中有 n 个节点并按从 1 到 n 给节点编号另给你一个数组 edges 其中每个 edges[i] [ui, vi, weighti] 表示存在一条位于节点 ui 和 vi 之间的边这条边的权重为 weighti 。
从节点 start 出发到节点 end 的路径是一个形如 [z0, z1, z2, ..., zk] 的节点序列满足 z0 start 、zk end 且在所有符合 0 i k-1 的节点 zi 和 zi1 之间存在一条边。
路径的距离定义为这条路径上所有边的权重总和。 用 distanceToLastNode(x) 表示节点 n 和 x 之间路径的最短距离。 受限路径 为满足 distanceToLastNode(zi) distanceToLastNode(zi1) 的一条路径其中 0 i k-1 。
返回从节点 1 出发到节点 n 的 受限路径数 。 由于数字可能很大请返回对 10^9 7 取余 的结果。
示例 1
输入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示例 2
输入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
任意两个节点之间至多存在一条边
任意两个节点之间至少存在一条路径来源力扣LeetCode 链接https://leetcode-cn.com/problems/number-of-restricted-paths-from-first-to-last-node 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
先预处理出每个点 到 n 点 的最短路径参考迪杰斯特拉算法再建立 1 开始的最短路径是递减的 新图同时记录节点的入度采用 拓扑排序累积前一个节点转移过来的方案数
typedef pairint, int pii;
struct cmp{bool operator()(pii a, pii b) const{return a.first b.first;}
};
class Solution {
public:int countRestrictedPaths(int n, vectorvectorint edges) {// 建图迪杰斯特拉 求解 每个节点到 n 的最短距离 disvectorunordered_mapint,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];}vectorint dis(n, INT_MAX);priority_queuepii, vectorpii, 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 递减图并记录入度vectorint indegree(n, 0);unordered_mapint,unordered_setint g2;queueint q1;q1.push(0);unordered_setint 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 1e97;vectorlong long ans(n, 0);ans[0] 1;queueint 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;}
};676 ms 174 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
