题解
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
好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱
2025-08-07 来自 上海
0好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱好可爱
2025-08-06 来自 上海
0
有帮助，赞一个