Advertisement
Saleh127

UVA 10048 / Floyd-Warshall

Nov 12th, 2021
681
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-12-18.47.06
  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[505][505];
  13.  
  14. int main()
  15. {
  16.     ios_base::sync_with_stdio(0);
  17.     cin.tie(0);
  18.     cout.tie(0);
  19.  
  20.     ll n,m,i,j,k,l,q,cc=0;
  21.  
  22.     while(cin>>n>>m>>q && n && m && q)
  23.     {
  24.         for(i=0; i<=n; i++)
  25.         {
  26.             for(j=0; j<=n; j++)
  27.             {
  28.                 cost[i][j]=1e17;
  29.             }
  30.             cost[i][i]=0ll;
  31.         }
  32.  
  33.  
  34.         for(i=0; i<m; i++)
  35.         {
  36.             cin>>j>>k>>l;
  37.  
  38.             cost[j][k]=min(cost[j][k],l);
  39.             cost[k][j]=min(cost[k][j],l);
  40.         }
  41.  
  42.  
  43.         for(k=1; k<=n; k++)
  44.         {
  45.             for(i=1; i<=n; i++)
  46.             {
  47.                 for(j=1; j<=n; j++)
  48.                 {
  49.                     cost[i][j]=min(cost[i][j],max(cost[i][k],cost[k][j]));
  50.                 }
  51.             }
  52.         }
  53.  
  54.         if(cc) cout<<nl;
  55.  
  56.         cout<<"Case #"<<++cc<<nl;
  57.  
  58.         while(q--)
  59.         {
  60.             cin>>j>>k;
  61.  
  62.             if(cost[j][k]==1e17) cout<<"no path"<<nl;
  63.  
  64.             else cout<<cost[j][k]<<nl;
  65.         }
  66.  
  67.     }
  68.  
  69.     get_lost_idiot;
  70. }
  71.  
  72.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement