[C++] 純文本查看 復制代碼
/*
UVA 104
AC
56ms
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n;
double list[32][32][32]; // [j][p] min dist of after
int through[32][32][32];
double target = 1.01;
void recover(int i, int j, int p)
{
if(p==0)
return;
if(through[j][p] != -1)
recover(i, through[j][p], p-1);
printf("%d ",through[j][p]);
}
void SP()
{
for(int p = 1 ; p <= n ; p++)
{
//update
for(int k = 1 ; k <= n ; k++)
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
if(list[k][p-1]*list[k][j][0] > list[j][p])
{
list[j][p] = list[k][p-1]*list[k][j][0];
through[j][p] = k;
}
//check
for(int i = 1 ; i <= n ; i++)
{
if(list[p] >= target)
{
printf("%d ",i);
recover(i,i,p);
printf("%d\n",i);
return;
}
}
}
puts("no arbitrage sequence exists");
return;
}
int main()
{
while(~scanf("%d",&n))
{
//init
memset(list,0,sizeof(list));
memset(through, -1, sizeof(through));
//input
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
if(i!=j)
scanf("%lf", &list[j][0]);
SP();
}
return 0;
}