Advertisement
NgJaBach

Floyd Warshall

Jan 26th, 2022
974
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long int ll;
  5. //#define isvowel(a) (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define gcd __gcd
  11. #define getl(s) getline(cin, s);
  12. #define setpre(x) fixed << setprecision(x)
  13. #define mset(a) memset(a, 0, sizeof(a))
  14. #define endl '\n'
  15. const int N=1050,M=1000000007;
  16. const ll INF=1e18+7;
  17. int main(){
  18.     ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
  19. //    freopen(".inp","r",stdin);
  20. //    freopen(".out","w",stdout);
  21.     ll n,m,q,x,y,z,graph[N][N];
  22.     cin>>n>>m;
  23.     for(int i=1;i<=n;++i){
  24.         for(int j=1;j<=n;++j){
  25.             if(i==j) graph[i][j]=0;
  26.             else graph[i][j]=INF;
  27.         }
  28.     }
  29.     for(int i=0;i<m;++i){
  30.         cin>>x>>y>>z;
  31.         graph[x][y]=z;
  32.     }
  33.     for(int k=1;k<=n;++k){
  34.         for(int i=1;i<=n;++i){
  35.             for(int j=1;j<=n;++j){
  36.                 graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
  37.             }
  38.         }
  39.     }
  40.     for(int i=1;i<=n;++i){
  41.         for(int j=1;j<=n;++j){
  42.             if(graph[i][j]==INF) graph[i][j]=-1;
  43.         }
  44.     }
  45.     cin>>q;
  46.     while(q--){
  47.         cin>>x>>y;
  48.         cout<<graph[x][y]<<endl;
  49.     }
  50.     return 0;
  51. }
  52. /*
  53. ==================================+
  54. INPUT:                            |
  55. ------------------------------    |
  56.  
  57. ------------------------------    |
  58. ==================================+
  59. OUTPUT:                           |
  60. ------------------------------    |
  61.  
  62. ------------------------------    |
  63. ==================================+
  64. */
  65.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement