fork(5) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. struct edge{
  7.     int from, to, cost;
  8. };
  9. const int INF = 1e9;;
  10.  
  11. int main(){
  12.     int n;
  13.     cin >> n;
  14.     vector <edge> E;
  15.     for(int i = 0; i < n; i++){
  16.         for(int j = 0; j < n; j++){
  17.             int x;
  18.             cin >> x;
  19.             if(x != 0 && x != 100000){
  20.                 E.push_back({i,j,x});
  21.             }
  22.         }
  23.     }
  24.     int x ;
  25.     vector<int> d(n, INF), p(n, -1);
  26.     d[0] = 0;
  27.     for(int i = 0; i < n; i++){
  28.         x = -1;
  29.         for(int j = 0; j < E.size(); j++){
  30.             int from = E[j].from;
  31.             int to = E[j].to;
  32.             int cost = E[j].cost;
  33.             if(d[to] > d[from] + cost ){
  34.                 d[to] = max(d[from] + cost, -INF);
  35.                 p[to] = from;
  36.                 x = to;
  37.             }
  38.         }
  39.     }
  40.     if(x == -1){
  41.         cout << "NO" << endl;
  42.     }else{
  43.         int y = x;
  44.         for(int i = 0; i < n; i++){
  45.             y = p[y];
  46.         }
  47.         vector <int> path;
  48.         for(int cur = y;; cur = p[cur]){
  49.             path.push_back(cur);
  50.             if(cur == y && path.size() > 1){
  51.                 break;
  52.             }
  53.         }
  54.         reverse(path.begin(), path.end());
  55.         cout << "YES" << endl;
  56.         cout << path.size() << endl;
  57.         for(int i = 0; i < path.size(); i++){
  58.             cout << path[i] + 1;
  59.             if(i != path.size()-1){
  60.                 cout << ' ';
  61.             }
  62.         }
  63.         cout << endl;
  64.     }
  65.     return 0;
  66. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
3
0 2 3
2 0 1
3 1 0
stdout
copy 
NO
https://ideone.com/wA4De0
language:
C++14 (gcc 8.3)
created:
8 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!