Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define _test int _TEST; cin>>_TEST; while(_TEST--)
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- _test
- {
- ll int n, m;
- cin>>n>>m;
- vector<vector<pair<ll int, ll int>>> graph(n+1);
- for(int i=0; i<m; i++)
- {
- ll int a, b, d;
- cin>>a>>b>>d;
- graph[a].push_back({b, -d});
- graph[b].push_back({a, d});
- }
- map<ll int, set<int>> mp;
- ll int f = 1;
- vector<ll int> vis(n+1);
- function <void(ll int, ll int)> DFS = [&](ll int u, ll int dist)
- {
- mp[dist].insert(u);
- vis[u] = 1;
- for(auto [v, d]: graph[u])
- {
- if(!vis[v])
- DFS(v, dist+d);
- else
- f &= (mp[dist+d].find(v) != mp[dist+d].end());
- }
- };
- for(int i=1; i<=n && f; i++)
- {
- if(vis[i]) continue;
- mp.clear();
- DFS(i, 0);
- }
- if(f) cout<<"YES\n";
- else cout<<"NO\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment