一本通网站上不去，截图为证
还是要整博客的。。。
目前学了FloydO（n3）和dijkstra算法O（n2）
Floyd是把每个点都遍历一遍，而后者只针对单个起点所以前者慢，但前者可以处理负边权（边的长度）。
下面是一道例题（数据较小用了Floyd）：
中山路上有n（n<=100）家店，每家店的坐标均在-10000~10000之间。其中的m家店之间有通路。若有通路，则表示可以从一家店走到另一家店，通路的距离为两点间的直线距离。现在要找出从一家店到另一家店之间的最短距离。
代码：
#include<bits/stdc++.h> using namespace std; int a[105][3]; double f[105][105]; int n,i,j,k,x,y,m,s,e; int main(){ scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&a[i][1],&a[i][2]); scanf("%d",&m); memset(f,0x7f,sizeof(f)); //附一个超大的值，方便下面考虑最短路径 for(i=1;i<=m;i++){ scanf("%d%d",&x,&y); f[x][y]=(sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2))); //计算边权，也可以写成函数 f[y][x]=f[x][y]; } scanf("%d%d",&s,&e); for(k=1;k<=n;k++){ for(i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if((i!=j)&&(j!=k)&&(i!=k)&&(f[i][k]+f[k][j]<f[i][j])) //Floyd主要部分，遍历每个结点之间的最短路径，将k视为中间节点 f[i][j]=f[i][k]+f[k][j]; } } } printf("%0.2lf",f[s][e]); return 0; }
整个就是模板题，主要用来熟练思路
原文：https://www.cnblogs.com/648-233/p/10744072.html