Table of Contents
Problem link
Hints
Floyd-Warshall algorithm
Solution code
#include<cstdio> #include<cstring> using namespace std; void floyd(int n); void print(int x, int y, int p); #define N 20 int seq[N][N][N]; double table[N][N][N]; int main(void){ int n; while(scanf("%d",&n) != EOF){ memset(seq,0,sizeof(seq)); memset(table,0,sizeof(table)); for(int i=0;i<n;++i) for(int j=0;j<n;++j) if( i != j){ scanf("%lf",&table[i][j][0]); seq[i][j][0]=i; } floyd(n); } return 0; } void floyd(int n){ for(int p=1;p<n;++p){ for(int i=0;i<n;++i) for(int k=0;k<n;++k) for(int j=0;j<n;++j) if(table[i][k][p-1]*table[k][j][0] > table[i][j][p]){ table[i][j][p] = table[i][k][p-1]*table[k][j][0]; seq[i][j][p]=k; } for(int i=0;i<n;++i){ if(table[i][i][p] > 1.01){ print(i,i,p); printf("\n"); return; } } } printf("no arbitrage sequence exists\n"); } void print(int x, int y, int p){ if(p == -1){ printf("%d",x+1); }else{ print(x,seq[x][y][p],p-1); printf(" %d",y+1); } }