Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2018
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. struct edge {
  6.     int a, b, cost;
  7. };
  8.  
  9. int n, m;
  10. vector<edge> e;
  11. const int INF = 1000000000;
  12.  
  13. void solve() {
  14.     vector<int> d (n);
  15.     vector<int> p (n, -1);
  16.     int x;
  17.     for (int i=0; i<n; ++i) {
  18.         x = -1;
  19.         for (int j=0; j<m; ++j)
  20.             if (d[e[j].b] > d[e[j].a] + e[j].cost) {
  21.                 d[e[j].b] = max (-INF, d[e[j].a] + e[j].cost);
  22.                 p[e[j].b] = e[j].a;
  23.                 x = e[j].b;
  24.             }
  25.     }
  26.  
  27.     if (x == -1)
  28.         cout << "NO";
  29.     else {
  30.         int y = x;
  31.         for (int i=0; i<n; ++i)
  32.             y = p[y];
  33.  
  34.         vector<int> path;
  35.         for (int cur=y; ; cur=p[cur]) {
  36.             path.push_back (cur);
  37.             if (cur == y && path.size() > 1)  break;
  38.         }
  39.         //reverse (path.begin(), path.end());
  40.         int min_ = n + 2;
  41.         for (auto i : path) {
  42.             if (min_ > i) min_ = i;
  43.         }
  44.         cout << "YES" << endl << min_;
  45.     }
  46. }
  47. int main() {
  48.     cin >> n >> m;
  49.     e.resize(m);
  50.     for (int i = 0; i < m; ++i) {
  51.         cin >> e[i].a >> e[i].b >> e[i].cost;
  52.     }
  53.     solve();
  54.     return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement