OJ-T00104: Arbitrage

#include <bits/stdc++.h>
using namespace std;

const int N = 20 + 5;

double dist[N][N][N];
int pr[N][N][N];

int main(){

    int nVertex;
    while(scanf("%d", &nVertex) != EOF){
        for(int u = 1; u <= nVertex; ++u){
            for(int v = 1; v <= nVertex; ++v){
                if(u == v){
                    dist[1][u][u] = 0;
                } else {
                    scanf("%lf", &dist[1][u][v]);
                    dist[1][u][v] = -log(dist[1][u][v]);
                }
                pr[1][u][v] = u;
            }
        }
        for(int c = 2; c <= nVertex; ++c){
            for(int u = 1; u <= nVertex; ++u){
                for(int v = 1; v <= nVertex; ++v){
                    dist[c][u][v] = 1e308;
                }
            }
        }
        for(int c = 2; c <= nVertex; ++c){
            for(int k = 1; k <= nVertex; ++k){
                for(int u = 1; u <= nVertex; ++u){
                    for(int v = 1; v <= nVertex; ++v){
                        if(dist[c - 1][u][k] + dist[1][k][v] < dist[c][u][v]){
                            dist[c][u][v] = dist[c - 1][u][k] + dist[1][k][v];
                            pr[c][u][v] = k;
                        }
                    }
                }
            }
        }
        double tr = -log(1.01);
        int cnt = 0;
        int st = 0;
        for(int c = 2; c <= nVertex; ++c){
            for(int u = 1; u <= nVertex; ++u){
                if(dist[c][u][u] < tr){
                    cnt = c;
                    st = u;
                    goto printPath;
                }
            }
        }
        cout << "no arbitrage sequence exists\n";
        continue;
        printPath:
        stack<int> stk;
        int cur = st;
        stk.push(st);
        for(; cnt >= 1; --cnt){
            cur = pr[cnt][st][cur];
            stk.push(cur);
        }
        while(stk.size() > 1){
            cout << stk.top() << ' ';
            stk.pop();
        }
        cout << stk.top() << '\n';
    }

    return 0;
}