P1286 最短路径 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2024年6月25日 15:26

最短路径题解：最小生成树+SPFA遍历即可

P1286

回复 0 | 赞 0 | 浏览 519

//#include <bits/stdc++.h> #include <iostream> #include <algorithm> #include <unordered_map> #include <queue> using namespace std; #define maxn 205 #define maxm 1010 #define INF 0x3f3f3f3f #define for_(i,a,b) \ for(int i = (a); i < (...

2023年1月15日 16:50

堆优化dijkstra+并查集

P1286

回复 0 | 赞 1 | 浏览 3.8k

#include using namespace std; typedef long long ll; const int N=300086; typedef pair PII; int n,m,s1; // 点的数量 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储所有点到1号点的距离 bool st[N]; // 存储每个点的最短距离是否已确定 const int INF=100086; int a,b,res=0,maxx; ...

想想y总会怎么做

2022年2月27日 17:40

披着最短路径皮的MST问题

P1286

回复 0 | 赞 0 | 浏览 7.6k

借鉴大佬的思路，真跪了https://blog.csdn.net/qq_33890670/article/details/79703197 https://www.nowcoder.com/practice/a29d0b5eb46b4b90bfa22aa98cf5ff17?tpId=62&tqId=29464&tPage=1&ru=/kaoyan/retest/2002&qru=/ta/sju-kaoyan/question-ranking 本题核心：第k条路径的长度为2^K，则第k条路径的长度会大于前k-1条路径的总和。由此我们可以推...

2021年8月30日 21:37

SPFA解法及两点注意

P1286

回复 0 | 赞 0 | 浏览 7.7k

1.如果点a到b已连通，那么再遇到a到b的边就不应该再加入，因为2^k>1+2^1+.......+2^k-1,如果无脑添加的话就会有数据点出错，这跟通用的最短路径解法有出入，但是为什么加入会出错我搞不懂求大佬解释,因为遍历的话应该能算出最小路径啊，难道它的数据点里有重复的边...... 2.数据溢出问题每次加入两点距离时都应该%100000，否则一直累加就会数据溢出。 #include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f const int maxn = 105...

2021年3月15日 10:50

题为最短路径，实则是最小生成树

P1286

回复 0 | 赞 0 | 浏览 9.5k

每条边长2^K, k<=500, 若k<=64还能用Dij,相加直接用位运算即可。而k最大可达500，还要取模，取模后不能比较大小 //将Dijkstra算法得到的n-1条路径求并集U //1.必不存在环。因为每个结点必和前驱结点共用路径 //2.必为连通图。源点可达任意结点 //可知并集U必为生成树。不一定为最小生成树(可用三角形图举反例) //若图任意边权值>更小边总和，则各最短路径的并集一定是最小生成树，2^k >2^(k-1)+...+1 //证: 在最小生成树上任意增加一边E构成环，由最小生成树性质可知E为环上最大...

2021年2月19日 19:43

dijkstra

P1286

回复 0 | 赞 0 | 浏览 8.1k

#include <iostream> #include <math.h> #include <string.h> using namespace std; const int maxn=105; int g[maxn][maxn]; int dist[maxn]; int vis[maxn]; int n,m; int dijkstra(){ dist[0]=0; for(int i=0;i<n;i++){ &n...

题目最短路径

题解数量6

热门题解

1 堆优化dijkstra+并查集

2 披着最短路径皮的MST问题

3 最短路径题解：最小生成树+SPFA遍历即可

4 SPFA解法及两点注意

5 题为最短路径，实则是最小生成树

6 dijkstra