Floyd-warshall求解最短路的思路：
通过第1~n每个顶点试图对任意一对顶点间距离进行“松弛”
所谓松弛 就是指通过某个顶点使其他顶点对间距离缩短
floyd的核心代码也正是这么干的emm
for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(mp[i][j] > mp[i][k] + mp[k][j]) mp[i][j] = mp[i][k] + mp[k][j];
非常简单粗暴的O(N^3)的时间复杂度（因为需要通过顶点直接访问边，邻接矩阵存图较为合适）
而且emmm 因为N^3的时间复杂度，也不用担心数组开不了这么大的问题了。。开不了的 它也一定跑不过去
然后…
因为用邻接矩阵存图，就有一个平行边的问题=-=
在最短路问题里，解决方法当然是……
while(m--){ int a, b, c; a = read(); b = read(); c = read(); mp[a][b] = min(mp[a][b], c); }
存短的边啦！
然后floyd相比bellman-ford/dijkstra虽然复杂度比较高，但是可以求出任意两点的最短路径，均摊到每个点对上而言
还是算不错的时间复杂度
然后稍微贴道题吧…w
洛谷P1629 邮递员送信https://www.luogu.com.cn/problem/P1629
题目大意：邮递员从结点1往2~n号结点送包裹，每送完一件需要返回邮局，求邮递员完成邮递的最短路径
边均为有向边且题目保证图连通（n<=10^3)
（qwq一开始以为是无向图，直接dijkstra 然后把距离一加 *2 然后样例都过不去。。）
由于是有向图，需要求出结点1到其他点的最短路与其他点到结点1的最短路
然后数据不算大，可以考虑floyd+卡常ac
（这里正解比较巧（其实是我菜orz），同时正向建边和反向建边跑两次dijkstra即可）
贴个ac代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 1e3 + 5, inf = 0x3f3f3f3f; int mp[maxn][maxn]; int n, m; inline int read(){ int x = 0,f = 1; char ch = getchar(); while(!isdigit(ch)){if(ch == '-') f=-1; ch = getchar();} while(isdigit(ch)){x=x*10 + ch - '0'; ch = getchar();} return x*f; } int ans; int main(){ n = read(); m = read(); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i != j) mp[i][j] = inf; else mp[i][j] = 0; while(m--){ int a, b, c; a = read(); b = read(); c = read(); mp[a][b] = min(mp[a][b], c); } for(int k = 1; k <= n; k++) for(ri int i = 1; i <= n; i++) for(ri int j = 1; j <= n; j++) if(mp[i][j] > mp[i][k] + mp[k][j]) mp[i][j] = mp[i][k] + mp[k][j]; for(int i = 2; i <= n; i++) ans += mp[1][i] + mp[i][1]; printf("%d", ans); return 0; }
大概就是读入优化+O2优化可以过掉。。不开O2会T掉几个点emm 不过本来就不是正解了
嗯=-= 如果数据不大的话，floyd还是很好的（Emm至少很好写）