fork(5) download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. struct Edge {
  7.     int st, en, cost;
  8. };
  9.  
  10. const int INF = 1000000000;
  11.  
  12. vector<Edge> edges;
  13.  
  14. int N, M, W;
  15.  
  16. bool hasNegative() {
  17.     vector<int> dist(N + 1, INF);
  18.     dist[1] = 0;
  19.  
  20.     for (int i = 0; i < N + 1; i ++) {
  21.         bool updated = false;
  22.  
  23.         for (auto &e : edges) {
  24.             if (dist[e.en] > dist[e.st] + e.cost) {
  25.                 dist[e.en] = dist[e.st] + e.cost;
  26.                 updated = true;
  27.             }
  28.         }
  29.         if (!updated) {
  30.             return false;
  31.         }
  32.     }
  33.  
  34.     return true;
  35. }
  36.  
  37. int main() {
  38.     int T;
  39.     scanf("%d", &T);
  40.  
  41.     while (T --) {
  42.         scanf("%d %d %d", &N, &M, &W);
  43.  
  44.         for (int i = 0; i < M; i ++) {
  45.             int a, b, c;
  46.             scanf("%d %d %d", &a, &b, &c);
  47.             edges.push_back({a, b, c});
  48.             edges.push_back({b, a, c});
  49.         }
  50.  
  51.         for (int i = 0; i < W; i ++) {
  52.             int a, b, c;
  53.             scanf("%d %d %d", &a, &b, &c);
  54.             edges.push_back({a, b, -c});
  55.         }
  56.  
  57.         if (hasNegative()) {
  58.             printf("YES\n");
  59.         } else {
  60.             printf("NO\n");
  61.         }
  62.         edges.clear();
  63.     }
  64.     return 0;
  65. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
stdout
copy 
NO
YES
https://ideone.com/Qig10t
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!