# Poj Solution 1476

```http://poj.org/problem?id=1476

#include<stdio.h>

#define debug 0
#define NMAX 20
#define DMAX 30
#define INF 1000000000
#define KMAX 1001
long d[KMAX][NMAX];
int main()
{

#if debug
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif

int T=1,N,K,i,j,k;
long c[NMAX+1][NMAX+1][DMAX+1];
int t[NMAX+1][NMAX+1];
scanf("%d%d",&N,&K);
while(N&&K)
{
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{
if(i!=j)
{
scanf("%d",&t[i][j]);
for(k=1;k<=t[i][j];k++)
{

scanf("%ld",&c[i][j][k]);

}
}
else
{
t[i][j]=0;
}
}
k=K;
for(i=1;i<N;i++)
{
if(c[i][N][(k-1)%t[i][N]+1]==0)
d[k][i]=INF;
else
d[k][i]=c[i][N][(k-1)%t[i][N]+1];
}
d[k][N]=INF;
for(k=K-1;k>=1;k--)
{
for(i=1;i<=N;i++)
{
d[k][i]=INF;
for(j=1;j<=N;j++)
{
if(i!=j&&c[i][j][(k-1)%t[i][j]+1]&&d[k][i]>c[i][j][(k-1)%t[i][j]+1]+d[k+1][j])
{
d[k][i]=c[i][j][(k-1)%t[i][j]+1]+d[k+1][j];
}
}
}
}
printf("Scenario #%dn",T);

if(d[1][1]!=INF)
printf("The best flight costs %ld.nn",d[1][1]);
else
printf("No flight possible.nn");

scanf("%d%d",&N,&K);
T++;
}

#if debug
fclose(stdin);
fclose(stdout);
#endif;
return 1;
}
```
This entry was posted in poj. Bookmark the permalink.