Advertisement
Hippskill

Untitled

Jan 20th, 2016
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #define _USE_MATH_DEFINES
  2. #include<stdio.h>
  3. #include<iostream>
  4. #include<vector>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<memory.h>
  8. #include<map>
  9. #include<set>
  10. #include<queue>
  11. #include<list>
  12. #include<sstream>
  13. #include<cstring>
  14. #include<numeric>
  15. #include<limits.h>
  16. #include<stack>
  17. using namespace std;
  18.  
  19.  
  20.  
  21.  
  22. const int N = 1e2 + 1;
  23. const int S = 1e6 + 1;
  24.  
  25. int s;
  26. vector<pair<int, int>> g[N];
  27. set<int> gs[N];
  28.  
  29.  
  30.  
  31. bool mu = false;
  32. bool k = false;
  33.  
  34. void addEdge(int a, int b, int c) {
  35.     g[a].push_back(make_pair(b, c));
  36.     g[b].push_back(make_pair(a, c));
  37.     if (a == b) {
  38.         k = true;
  39.     }
  40.     if (gs[a].count(b) != 0) {
  41.         mu = true;
  42.     }
  43.     if (gs[b].count(a) != 0) {
  44.         mu = true;
  45.     }
  46.     gs[a].insert(b);
  47.     gs[b].insert(a);
  48. }
  49.  
  50.  
  51. bool u[N];
  52. bool c = false;
  53. int p[N];
  54.  
  55. void dfsCycle(int v) {
  56.     u[v] = true;
  57.     for (auto to : g[v]) {
  58.         if (u[to.first]) {
  59.             if (p[v] != to.first) {
  60.                 c = true;
  61.                 return;
  62.             }
  63.         }
  64.         else {
  65.             p[to.first] = v;
  66.             dfsCycle(to.first);
  67.         }
  68.     }
  69. }
  70.  
  71. bool used[N][S];
  72.  
  73. struct edge {
  74.     int a, b, cost;
  75.     edge(int a, int b, int cost) : a(a), b(b), cost(cost) {}
  76. };
  77. vector<edge> e;
  78.  
  79. int n, m;
  80. int fb(int s) {
  81.     vector<int> d(n, LONG_MAX);
  82.     d[s] = 0;
  83.     for (int i = 0; i < n - 1; i++)
  84.         for (int j = 0; j<m; j++)
  85.             if (d[e[j].a] < LONG_MAX)
  86.                 d[e[j].b] = min(d[e[j].b], d[e[j].a] + e[j].cost);
  87.     int res = 0;
  88.     for (int i = 0; i < n; i++) {
  89.         res = max(res, -d[i]);
  90.     }
  91.     return res;
  92. }
  93.  
  94. int main() {
  95. #ifndef ONLINE_JUDGE
  96.     freopen("input.txt", "r", stdin);
  97. #endif
  98.     scanf("%d%d%d", &n, &m, &s);
  99.     for (int i = 0; i < m; i++) {
  100.         int a, b, c;
  101.         scanf("%d%d%d", &a, &b, &c);
  102.         addEdge(a - 1, b - 1, c);
  103.         e.push_back(edge(a - 1, b - 1, -c));
  104.     }
  105.     for (int i = 0; i < n; ++i) {
  106.         if (!u[i]) {
  107.             dfsCycle(i);
  108.             if (c)
  109.                 break;
  110.         }
  111.     }
  112.  
  113.     if (c || mu || k) {
  114.         printf("YES");
  115.         return 0;
  116.     }
  117.  
  118.  
  119.     int res = 0;
  120.  
  121.     for (int i = 0; i < n; i++) {
  122.         res = max(res, fb(i));
  123.     }
  124.  
  125.    
  126.     printf(res >= s ? "YES" : "NO");
  127.  
  128.    
  129.     return 0;
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement