Floyd算法

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn=100;
 5 const int oo=10000000;
 6 int n,m;
 7 int dis[maxn][maxn];
 8 int main()
 9 {
10     scanf("%d%d",&n,&m);
11     for (int i=1;i<=n;i++) 
12      for (int j=1;j<=n;j++)
13       if (i!=j)
14        dis[i][j]=oo;
15     for (int i=1;i<=m;i++)
16     {
17         int x,y,z;
18         scanf("%d%d%d",&x,&y,&z);
19         dis[x][y]=min(dis[x][y],z);
20     }
21     for (int k=1;k<=n;k++)
22      for (int i=1;i<=n;i++)
23       for (int j=1;j<=n;j++)
24        if (dis[i][k]!=oo && dis[k][j]!=oo)
25         dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
26     for (int i=1;i<=n;i++)
27     {
28         for (int j=1;j<=n;j++) printf("%d ",dis[i][j]);
29         printf("\n");
30     }
31     return 0;
32  }