Floyd算法
2020-12-12 21:06
阅读：403
第一行两个整数n，m表示图中结点数和边的数量, 结点从1到n编号。
接下来m行，每行三个整数u，v，w表示u，v之间有一条距离为w的边。
接下来一行一个整数q，表示询问次数。
接下来q行每行两个整数u，v，表示询问u到v的最短距离， 如果u不能到达v输出-1。
那么我们简单介绍一下弗洛伊德算法
简单来说弗洛伊德算法就是不断枚举，“借东风”，复杂度比较高
for(k=1;ke[i][k]+e[k][j] )
e[i][j]=e[i][k]+e[k][j];
这是我的代码
#include
#include
#include
#include
using namespace std;
const int M=1005;
const int inf=0x3f3f;
int n,m;
int map[M][M];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i for(int j=1;j map[i][j]=inf;
for(int i=0;i map[i][i]=0;
while(m--)
{
int u,v,w;
cin>>u>>v>>w;
map[u][v]=min(map[u][v],w);
map[v][u]=map[u][v];
}
for(int i=1;i for(int j=1;j for(int k=1;k {
map[j][k]=min(map[j][k],map[j][i]+map[i][k]);
}
int y;cin>>y;
while(y--)
{
int q,e;cin>>q>>e;
cout }
return 0;
}
下一篇：常用的C++ STL
评论
亲，登录后才可以留言！