UVA 104 / Modified Floyd Warshall

/***
 created: 2022-05-27-23.42.37
***/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n;

    while(cin>>n && n)
    {
        double a[n+2][n+2][n+2];

        ll p[n+2][n+2][n+2],i,j,k,l=0;

        memset(a,0,sizeof a);

        memset(p,0,sizeof p);

        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(i==j)
                {
                    a[i][j][1]=1.00;
                }
                else
                {
                    cin>>a[i][j][1];
                }

                p[i][j][1]=j;
            }
        }


        for(ll stp=2;stp<=n;stp++)
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    for(k=1;k<=n;k++)
                    {
                        if(a[i][j][stp]<(a[i][k][stp-1]*a[k][j][1]))
                        {
                            a[i][j][stp]=(a[i][k][stp-1]*a[k][j][1]);
                            p[i][j][stp]=k;
                        }
                    }
                }
            }
        }

        vector<ll>seq;


        for(ll stp=2;stp<=n && !l;stp++)
        {
            for(i=1;i<=n && !l;i++)
            {
                if(a[i][i][stp]>1.01)
                {
                    l=1;

                    j=i;

                    seq.push_back(j);


                    for(k=stp;k>1;k--)
                    {
                        j=p[i][j][k];
                        seq.push_back(j);
                    }
                    seq.push_back(i);
                    break;
                }
            }
        }
        if(!l) cout<<"no arbitrage sequence exists"<<nl;
        else
        {
            for(i=seq.size()-1;i>=0;i--)
            {
                if(i==0) cout<<seq[i]<<nl;
                else cout<<seq[i]<<" ";
            }
        }
    }



    get_lost_idiot;
}