floyed算法模板

#include<bits/stdc++.h>
#include<vector>
using namespace std;
int lj[1010][1010];//邻接矩阵
//可以换成链式前向星之类的巴拉巴拉，这里用邻接矩阵演示比较清楚
int n,m;
int flyd[1001][1001];
int main(){
cin>>n>>m;
for (int i=1; i<=m; i++){
int u,v,w;
cin>>u>>v>>w;
lj[u][v]=w;
}
//输入边，权值
for (int i=1; i<=n; i++){//初始化
for (int j=1; j<=n; j++){
if (i==j) flyd[i][j]=0;
else if (lj[i][j]) flyd[i][j]=lj[i][j];
else{
flyd[i][j]=1000000000;
}
}
}
/*
从小到大，经过新的节点，可能使路径更短
时间复杂度较高

*/
for (int k=1; k<=n; k++){//每一个新节点进行更新，找到代价最小的路
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
flyd[i][j]=min(
flyd[i][j],
flyd[i][k]+flyd[k][j]
);
}
}
}
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
cout<<flyd[i][j]<<' ';
}
cout<<endl;
}
return 0;
}

/*
5 6
1 2 1
1 3 2
1 5 1
2 4 5
3 4 3
4 5 4

*/