题解
2025-08-06 20:16:20
发布于：上海
Floyd算法，我感觉是最短路算法里最简单的
#include <iostream>
#include <vector>
using namespace std;
const int INF=2e9;
const int N=648;
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>>dis(n+1,vector<int>(n+1,INF));
for(int i=1;i<=n;i++)dis[i][i]=0;//处理自环
for(int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
dis[u][v]=min(dis[u][v],w);//处理重边
}
//Floyd
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dis[i][k]<INF && dis[k][j]<INF)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
for(int i=1;i<=n;i++){
if(dis[i][i]<0){
cout<<"-1\n";
return 0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]>=INF)cout<<"1000000000 ";
else cout<<dis[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
全部评论 7
好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱
2天前 来自 上海
0好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱
2天前 来自 上海
0
有帮助，赞一个