Floyd多源最短路模板
2026-01-31 10:20:39
发布于：四川
1阅读
0回复
0点赞
//Floyd多源最短路模板
//B3647
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 501; //最大节点数 (n<=500)
int dis[maxn][maxn];//dis[i][j]：i到j的最短路径
int main(){
int n,m,u,v,w;//n节点数 m边数
cin>>n>>m;
memset(dis,inf,sizeof dis);//初始化为无穷大
for(int i=1;i<=m;++i){
cin>>u>>v>>w;//u=起点 v=终点 w=边权
if(w<dis[u][v]){//处理重边(只保留初始距离最短的直接边)
dis[u][v]=w;//处理无向图
dis[v][u]=w;
}
}
for(int i=1;i<=n;++i){
dis[i][i] = 0;//初始化自己到自己的距离(0)
}
//设置一个中介节点(k),用于连接i和j
//i到j的最短路径 = 原来i到j的路径 和 i到k到j的路径 的最小值
for(int k=1;k<=n;++k){//枚举中间节点 (k)
for(int i=1;i<=n;++i){//枚举起点 (i)
for(int j=1;j<=n;++j){//枚举终点(j)
//松弛操作：更新最短路径
dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
//输出
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
cout<<dis[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
这里空空如也
有帮助，赞一个