ccbeginner

UVa 558

Jan 24th, 2020
98
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Bellman-ford
  2. //UVa Q558
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. struct edge{
  7.     int u,v,w;
  8. }e[2000];
  9.  
  10. int dist[1000];
  11.  
  12. int32_t main(){
  13.     int n,m,t;
  14.     cin >> t;
  15.     while(t--){
  16.         cin >> n >> m;
  17.         dist[0] = 0;
  18.         for(int i = 1; i < n; ++i)dist[i] = 1e9;
  19.         for(int i = 0; i < m; ++i)cin >> e[i].u >> e[i].v >> e[i].w;
  20.         for(int i = 0; i < n-1; ++i){
  21.             for(int j = 0; j < m; ++j){
  22.                 dist[e[j].v] = min(dist[e[j].v], dist[e[j].u] + e[j].w);
  23.             }
  24.         }
  25.         bool possible = 0;
  26.         for(int i = 0; i < m; ++i){
  27.             if(dist[e[i].v] > dist[e[i].u]+e[i].w){
  28.                 possible = 1;
  29.                 break;
  30.             }
  31.         }
  32.         if(possible)cout << "possible\n";
  33.         else cout << "not possible\n";
  34.     }
  35.     return 0 ;
  36. }
RAW Paste Data