Advertisement
kaa7

Untitled

May 22nd, 2019
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MAXN 100001
  3. #define MAXM 200001
  4. using namespace std;
  5. struct edge{
  6. int nod, c;
  7. edge(int nod, int c):nod(nod), c(c) {}
  8. };
  9. vector<vector<edge>> G;
  10. char viz[MAXN];
  11. int n, m;
  12. int dg;
  13. int bfs(int nod, int caut, int cost) {
  14. //cout << "vizitez nodul " << nod << "cu costul " << cost << " caut " << caut << endl;
  15. if(nod == caut) {
  16. //cout << "am gasit cu costul " << cost << endl;
  17. dg = cost;
  18. }
  19. for(edge i : G[nod]) {
  20. if(viz[i.nod] == 0) {
  21. viz[i.nod] = 1;
  22. bfs(i.nod, caut, cost + i.c);
  23. }
  24. }
  25. return 0;
  26. }
  27. int main() {
  28. cin >> n >> m;
  29. G.resize(n+1);
  30. for(int i = 0; i < m; ++i) {
  31. int l, r, d;
  32. cin >> l >> r >> d;
  33. memset(viz, 0, MAXN);
  34. viz[l] = 1;
  35. //cout << "bfs pt " << l << endl;
  36. dg = 0;
  37. bfs(l, r, 0);
  38. //cout << "dg: " << dg << endl;
  39. //cout << "viz\n";
  40.  
  41. if(dg != d && dg != 0) {
  42. cout << "No\n";
  43. return 0;
  44. }
  45. G[l].push_back(edge(r, d));
  46. G[r].push_back(edge(l, -d));
  47. }
  48. cout << "Yes\n";
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement