• Source 
    1. #include <fstream>
    2. #include <iostream>
    3. #include <stdio.h>
    4. using namespace std;
    5. int n,m;
    6. int a[101][101],tr[101][101];
    7. const int oo=1000000;
    8. int main()
    9. {
    10.     ifstream fi("floyd.inp");
    11.     ofstream fo("floyd.out");
    12.     fi>>n>>m;
    13.     for(int i=1;i<=n;i++)
    14.         for(int j=1;j<=n;j++) {a[i][j]=oo; tr[i][j]=j;}
    15.      for(int i=1;i<=n;i++) a[i][i]=0;
    16.     for(int i=1;i<=m;i++)
    17.     {
    18.         int x,y,w;
    19.         fi>>x>>y>>w;
    20.         a[x][y]=w;
    21.     }
    22.     fo<<"D0"<<endl;
    23.     for(int i=1;i<=n;i++)
    24.     {
    25.         for(int j=1;j<=n;j++)
    26.             if(a[i][j]==oo) fo<<"oo "; else fo<<a[i][j]<<" ";
    27.         fo<<endl;
    28.     } fo<<endl;
    29.  
    30.     fo<<"P0"<<endl;
    31.     for(int i=1;i<=n;i++)
    32.     {
    33.         for(int j=1;j<=n;j++)
    34.             if(tr[i][j]==-1) fo<<"nil "; else fo<<tr[i][j]<<" ";
    35.         fo<<endl;
    36.     }
    37.     fo<<"================"<<endl;
    38.  
    39.  
    40.     for(int k=1;k<=n;k++)
    41.     {
    42.         for(int i=1;i<=n;i++)
    43.           for(int j=1;j<=n;j++)
    44.            if(a[i][k]!=oo && a[k][j]!=oo && a[i][j]>a[i][k]+a[k][j])
    45.            {
    46.              a[i][j]=a[i][k]+a[k][j];
    47.              tr[i][j]=tr[i][k];
    48.            }
    49.  
    50.  
    51.        fo<<"D"<<k<<endl;
    52.        for(int i=1;i<=n;i++)
    53.        {
    54.         for(int j=1;j<=n;j++)
    55.             if(a[i][j]==oo) fo<<"oo "; else fo<<a[i][j]<<" ";
    56.         fo<<endl;
    57.        } fo<<endl;
    58.  
    59.        fo<<"P"<<k<<endl;
    60.        for(int i=1;i<=n;i++)
    61.        {
    62.         for(int j=1;j<=n;j++)
    63.             if(tr[i][j]==-1) fo<<"nil "; else fo<<tr[i][j]<<" ";
    64.         fo<<endl;
    65.        }
    66.        fo<<"================"<<endl;
    67.     }
    68.  
    69.     for(int i=1;i<=n;i++)
    70.          for(int j=1;j<=n;j++)
    71.             if(i!=j)
    72.          {
    73.              int u=i,v=j;
    74.            fo<<"Do dai tu "<<u<<" den "<<v<<":"<<a[u][v]<<endl;
    75.            fo<<"  -Duong di: ";
    76.            do
    77.            {
    78.                 fo<<u<<"->";
    79.                 u=tr[u][v];
    80.            } while (u!=v);
    81.            fo<<u<<endl;
    82.  
    83.          }
    84.     fi.close();
    85.     fo.close();
    86. }
    87.  
    88.