jakaria_hossain

UVA - Wormholes

Jun 4th, 2019
112
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