Advertisement
Saleh127

CSES 1627 / Floyd-Warshall

Nov 12th, 2021
736
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);cout.tie(0);
  18.  
  19.    ll n,m,i,j,k,l,q;
  20.  
  21.    cin>>n>>m>>q;
  22.  
  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],cost[i][k]+cost[k][j]);
  50.              }
  51.         }
  52.    }
  53.  
  54.  
  55.    while(q--)
  56.    {
  57.         cin>>j>>k;
  58.  
  59.         if(cost[j][k]==1e17) cout<<-1<<nl;
  60.  
  61.         else cout<<cost[j][k]<<nl;
  62.    }
  63.  
  64.    get_lost_idiot;
  65. }
  66.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement