最短路问题
write a short introduce
朴素做法
write something
Code1
Code
多源最短路
比较好于理解与编写的是 Floyd 算法。
Code2
#include <iostream>
#include <iomanip>
#include <string.h>
using namespace std;
int n,m;
int g[105][105];
void addedge(int u,int v,int w)
{
g[u][v]=w;
return ;
}
void Floyd()
{
for(int k=1;k<=n;k++)
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
return ;
}
int main()
{
memset(g,0x3f,sizeof g);
cin>>n>>m;
for(int i=0;i<m;i++)
{
int u,v,w;
cin>>u>>v>>w;
addedge(u,v,w);
addedge(v,u,w);
}
Floyd();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j) cout<<setw(12)<<"0";
else cout<<setw(12)<<g[i][j];
}
cout<<endl;
}
return 0;
}
# input
6 5
1 2 3
2 6 8
6 5 1
2 3 5
3 6 1
# output
0 3 8 1061109567 10 9
3 0 5 1061109567 7 6
8 5 0 1061109567 2 1
1061109567 1061109567 1061109567 0 1061109567 1061109567
10 7 2 1061109567 0 1
9 6 1 1061109567 1 0
标签:int,短路,问题,Floyd,1061109567,include,addedge
From: https://www.cnblogs.com/RainCQwQ/p/-/shortest_path