1476.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#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 #%d\n",T);

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

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

#if debug
	fclose(stdin);
	fclose(stdout);
#endif;
	return 1;
}