Advertisement
Saleh127

UVA 125 / Floyd-Warshall

Nov 12th, 2021
668
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-12-23.56.47
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. ll cost[100][100];
  13.  
  14. int main()
  15. {
  16.     ios_base::sync_with_stdio(0);
  17.     cin.tie(0);
  18.     cout.tie(0);
  19.  
  20.  
  21.     ll n,m,i,j,k,l=0;
  22.  
  23.     while(cin>>m)
  24.     {
  25.         n=0;
  26.  
  27.         memset(cost,0,sizeof cost);
  28.  
  29.         while(m--)
  30.         {
  31.             cin>>j>>k;
  32.  
  33.             cost[j][k]=1;
  34.             n=max({n,j,k});
  35.         }
  36.  
  37.         for(k=0; k<=n; k++)
  38.         {
  39.             for(i=0; i<=n; i++)
  40.             {
  41.                 for(j=0; j<=n; j++)
  42.                 {
  43.                     if(cost[i][k] && cost[k][j])
  44.                     {
  45.                         cost[i][j]+=(cost[i][k]*cost[k][j]);
  46.                     }
  47.                 }
  48.             }
  49.         }
  50.  
  51.         for(k=0; k<=n; k++)
  52.         {
  53.             if(cost[k][k])
  54.             {
  55.                 for(i=0; i<=n; i++)
  56.                 {
  57.                     for(j=0; j<=n; j++)
  58.                     {
  59.                         if(cost[i][k] && cost[k][j])
  60.                         {
  61.                             cost[i][j]=-1;
  62.                         }
  63.                     }
  64.                 }
  65.             }
  66.         }
  67.  
  68.         cout<<"matrix for city "<<l++<<nl;
  69.  
  70.         for(i=0;i<=n;i++)
  71.         {
  72.              for(j=0;j<=n;j++)
  73.              {
  74.                   if(j) cout<<" "<<cost[i][j];
  75.                   else cout<<cost[i][j];
  76.              }
  77.  
  78.              cout<<nl;
  79.         }
  80.  
  81.     }
  82.  
  83.     get_lost_idiot;
  84. }
  85.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement