图论

一、弗洛伊德

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int INF = INT_MAX;
 4 int n,m,a[1001][1001],f[1001][1001];
 5 int main(){
 6     ios::sync_with_stdio(false);
 7     cin>>n>>m;
 8     for(int i=1;i<=n;i++){
 9         for(int j=1;j<=n;j++){
10             if(i==j) f[i][j]=0;
11             else f[i][j]=INF;
12         }
13     }
14     int a,b,c;
15     for(int i=0;i<m;i++){
16         cin>>a>>b>>c;
17         f[a][b]=c;
18     }
19     for(int k=1;k<=n;k++){
20         for(int i=1;i<=n;i++){
21             for(int j=1;j<=n;j++){
22                 if(f[i][j]>f[i][k]+f[k][j]){
23                     f[i][j]=f[i][k]+f[k][j];
24                 }
25             }
26         }
27     }
28     for(int i=1;i<=n;i++){
29         for(int j=1;j<=n;j++){
30             cout<<f[i][j]<<" ";
31         }
32         cout<<endl;
33     }
34     return 0;
35 }