SHARE
TWEET

UVA - Wormholes

jakaria_hossain Jun 4th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fast()(ios_base::sync_with_stdio(false),cin.tie(NULL));
  4.  
  5. struct connect
  6. {
  7.     int u;
  8.     int v;
  9.     int w;
  10. }eg[2020];
  11. int main()
  12. {
  13.     fast();
  14.     int t;
  15.     cin>>t;
  16.     while(t--)
  17.     {
  18.         int node,edge;
  19.         cin>>node>>edge;
  20.         for(int i=0;i<edge;i++)cin>>eg[i].u>>eg[i].v>>eg[i].w;
  21.         int distance[1005];
  22.         for(int i=1;i<=node;i++)distance[i]=INT_MAX;
  23.         distance[0]=0;
  24.         for(int i=0;i<node-1;i++)
  25.         {
  26.             for(int j=0;j<edge;j++)
  27.             {
  28.                 if(distance[eg[j].u]+eg[j].w<distance[eg[j].v])
  29.                     distance[eg[j].v]=distance[eg[j].u]+eg[j].w;
  30.             }
  31.         }
  32.         bool flag=false;
  33.         for(int i=0;i<edge;i++)
  34.         {
  35.             if(distance[eg[i].u]+eg[i].w<distance[eg[i].v])flag=true;
  36.         }
  37.         if(flag)cout<<"possible"<<endl;
  38.         else cout<<"not possible"<<endl;
  39.     }
  40.     return 0;
  41. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top