Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- const int INF = 1e9;
- struct edge {
- int a, b, cost;
- };
- vector<edge> e;
- int32_t main() {
- cin.tie(0);
- ios_base::sync_with_stdio(false);
- freopen("negcycle.in", "r", stdin);
- freopen("negcycle.out", "w", stdout);
- int n;
- cin >> n;
- for(int i = 0; i < n; i ++)
- for(int j = 0; j < n; j ++)
- {
- int c;
- cin >> c;
- if(c != INF)
- e.push_back({i, j, c});
- }
- vector<int> d(n);
- vector<int> p(n, -1);
- int x;
- for(int i = 0; i < n; i++) {
- x = -1;
- for(int j = 0; j < e.size(); j++)
- if (d[e[j].b] > d[e[j].a] + e[j].cost) {
- d[e[j].b] = max(-INF, d[e[j].a] + e[j].cost);
- p[e[j].b] = e[j].a;
- x = e[j].b;
- }
- }
- if (x == -1)
- cout << "NO\n";
- else {
- int y = x;
- for (int i=0; i<n; ++i)
- y = p[y];
- vector<int> path;
- for (int cur=y; ; cur=p[cur]) {
- path.push_back (cur);
- if (cur == y && path.size() > 1) break;
- }
- reverse (path.begin(), path.end());
- cout << "YES\n";
- cout << path.size() << "\n";
- for(int i=0; i<path.size(); ++i)
- cout << path[i] + 1 << ' ';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement