Advertisement
Saleh127

UVA 104 / Modified Floyd Warshall

May 27th, 2022
504
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-05-27-23.42.37
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. int main()
  13. {
  14.     ios_base::sync_with_stdio(0);
  15.     cin.tie(0);
  16.     cout.tie(0);
  17.  
  18.     ll n;
  19.  
  20.     while(cin>>n && n)
  21.     {
  22.         double a[n+2][n+2][n+2];
  23.  
  24.         ll p[n+2][n+2][n+2],i,j,k,l=0;
  25.  
  26.         memset(a,0,sizeof a);
  27.  
  28.         memset(p,0,sizeof p);
  29.  
  30.         for(i=1;i<=n;i++)
  31.         {
  32.             for(j=1;j<=n;j++)
  33.             {
  34.                 if(i==j)
  35.                 {
  36.                     a[i][j][1]=1.00;
  37.                 }
  38.                 else
  39.                 {
  40.                     cin>>a[i][j][1];
  41.                 }
  42.  
  43.                 p[i][j][1]=j;
  44.             }
  45.         }
  46.  
  47.  
  48.         for(ll stp=2;stp<=n;stp++)
  49.         {
  50.             for(i=1;i<=n;i++)
  51.             {
  52.                 for(j=1;j<=n;j++)
  53.                 {
  54.                     for(k=1;k<=n;k++)
  55.                     {
  56.                         if(a[i][j][stp]<(a[i][k][stp-1]*a[k][j][1]))
  57.                         {
  58.                             a[i][j][stp]=(a[i][k][stp-1]*a[k][j][1]);
  59.                             p[i][j][stp]=k;
  60.                         }
  61.                     }
  62.                 }
  63.             }
  64.         }
  65.  
  66.         vector<ll>seq;
  67.  
  68.  
  69.         for(ll stp=2;stp<=n && !l;stp++)
  70.         {
  71.             for(i=1;i<=n && !l;i++)
  72.             {
  73.                 if(a[i][i][stp]>1.01)
  74.                 {
  75.                     l=1;
  76.  
  77.                     j=i;
  78.  
  79.                     seq.push_back(j);
  80.  
  81.  
  82.                     for(k=stp;k>1;k--)
  83.                     {
  84.                         j=p[i][j][k];
  85.                         seq.push_back(j);
  86.                     }
  87.                     seq.push_back(i);
  88.                     break;
  89.                 }
  90.             }
  91.         }
  92.         if(!l) cout<<"no arbitrage sequence exists"<<nl;
  93.         else
  94.         {
  95.             for(i=seq.size()-1;i>=0;i--)
  96.             {
  97.                 if(i==0) cout<<seq[i]<<nl;
  98.                 else cout<<seq[i]<<" ";
  99.             }
  100.         }
  101.     }
  102.  
  103.  
  104.  
  105.     get_lost_idiot;
  106. }
  107.  
Advertisement
RAW Paste Data Copied
Advertisement