SHARE
TWEET

Untitled

AntonBelskiy Jan 15th, 2020 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <stdio.h>
  4. using namespace std;
  5. int const inf=1e8;
  6. struct edge{
  7. int a,b,c;
  8. };
  9. struct edge e [10000];
  10. int d[100];
  11. int p[100];
  12. int main()
  13. {freopen("negcycle.in","r",stdin);
  14. freopen("negcycle.out","w",stdout);
  15.     int n,m;cin>>n;m=-1;
  16. for (int i=0;i<n;i++){
  17.     for (int j=0;j<n;j++){
  18.        int x;cin>>x;   if (x!=100000){m++;e[m].a=i;e[m].b=j;e[m].c=x;}
  19.        if((i==j)&&(x<0)){cout<<"YES"<<endl<<1<<endl<<i+1;return 0;}
  20.        }}
  21.     int k=-1;
  22.     for (int i=0;i<n;i++){
  23.             k=-1;
  24.         for (int j=0;j<m;j++){
  25.               if (d[e[j].b]>d[e[j].a]+e[j].c){
  26.                 d[e[j].b]=max(-inf,d[e[j].a]+e[j].c);
  27.                 p[e[j].b]=e[j].a;k=e[j].b;}}}
  28.         if (k==-1){cout<<"NO";}else{
  29.                 cout<<"YES"<<endl;
  30.             for(int i=0;i<n;i++){
  31.                 k=p[k];
  32.             }
  33.             int y=k;int f=0;
  34.             vector <int> v;
  35.             for(int i=0;i<n;i++){
  36.                 if((i!=0)&&(y==k)){break;}else{v.push_back(y);y=p[y];f++;}}
  37.                 cout<<f<<endl;f--;
  38.             for(int i=f;i>-1;i--){
  39.                 cout<<v[i]+1<<" ";}}
  40.     return 0;
  41. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top