Description
第一行四个数为 n,m,n 表示顶点个数, m 表示边的条数.
接下来 m 行, 每一行有三个数 t1,t2 和 t3, 表示顶点 t1 到顶点 t2 的路程是 t3. 请注意这些 t1->t2 是单向的.
Output
输出一个 n*n 的矩阵, 第 n 行第 n 列表示定点 n 到 n 的距离. 每一行两个数间由空格隔开
- Sample Input
- 5 8
- 1 2 2
- 2 3 3
- 3 4 4
- 4 5 5
- 5 3 3
- 3 1 4
- 2 5 7
- 1 5 10
- Sample Output
- 0 2 5 9 9
- 7 0 3 7 7
- 4 6 0 4 9
- 12 14 8 0 5
- 7 9 3 7 0
- More Info
输出结果每行的最后一个数字后不需要留空格哦~
- #include<iostream>
- //#include<fstream>
- #define inf 0x3f3f3f3f
- using namespace std;
- int m,n;
- int e[1002][1002];
- int main(){
- // fstream file("haha.txt");
- // file>>n>>m;
- cin>>n>>m;
- for(int i=1;i<=n;i++){// 初始化
- for(int j=1;j<=n;j++){
- if(i==j)
- e[i][j]=0;
- else
- e[i][j]=inf;
- }
- }
- for(int i=1;i<=m;i++){// 录入
- int a,b,c;
- cin>>a>>b>>c;
- e[a][b]=c;
- }
- for(int k=1;k<=n;k++){// 弗洛伊德核心算法
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- if(e[i][j]>e[i][k]+e[k][j])
- e[i][j]=e[i][k]+e[k][j];
- }
- }
- }
- for(int i=1;i<=n;i++){// 输出
- for(int j=1;j<=n;j++){
- cout<<e[i][j];
- if(j!=n)
- cout<<" ";
- }
- cout<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3399367.html