Ankit_132

H

Jul 21st, 2023
306
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define ll     long long
  7. #define _test   int _TEST; cin>>_TEST; while(_TEST--)
  8.  
  9. int main()
  10. {
  11.     ios_base::sync_with_stdio(false);
  12.     cin.tie(NULL);
  13.     cout.tie(NULL);
  14.  
  15.     _test
  16.     {
  17.         ll int n, m;
  18.         cin>>n>>m;
  19.  
  20.         vector<vector<pair<ll int, ll int>>> graph(n+1);
  21.  
  22.         for(int i=0; i<m; i++)
  23.         {
  24.             ll int a, b, d;
  25.             cin>>a>>b>>d;
  26.  
  27.             graph[a].push_back({b, -d});
  28.             graph[b].push_back({a, d});
  29.         }
  30.  
  31.         map<ll int, set<int>> mp;
  32.         ll int f = 1;
  33.         vector<ll int> vis(n+1);
  34.  
  35.         function <void(ll int, ll int)> DFS = [&](ll int u, ll int dist)
  36.         {
  37.             mp[dist].insert(u);
  38.  
  39.             vis[u] = 1;
  40.  
  41.             for(auto [v, d]: graph[u])
  42.             {
  43.                 if(!vis[v])
  44.                     DFS(v, dist+d);
  45.                 else
  46.                     f &= (mp[dist+d].find(v) != mp[dist+d].end());
  47.             }
  48.         };
  49.  
  50.         for(int i=1; i<=n && f; i++)
  51.         {
  52.             if(vis[i])      continue;
  53.  
  54.             mp.clear();
  55.             DFS(i, 0);
  56.         }
  57.  
  58.         if(f)       cout<<"YES\n";
  59.         else        cout<<"NO\n";
  60.     }
  61. }
Advertisement
Add Comment
Please, Sign In to add comment