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.

Leave a Reply

Your email address will not be published. Required fields are marked *