UVA 590-Always on the run（DP）

题目大意：有若干城市，有些城市可以到达并且有花费，初始在城市1，要求旅游k天，并且最终在城市n，求是否能达到，若能求最小花费。

用d[i][j]表示第i天在城市j的最小花费，从d[i-1][u]递推而来，其中u是第i-1天所在的城市。

#include<stdio.h>
#include<stdlib.h>
int a[40][40][100];
int d[1100][30];
int main(void)
{
	int i,j,v,m,n,u,co;
	co=0;
	scanf("%d%d",&n,&m);
	while((n!=0)||(m!=0))
	{
		co++;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<i;j++)
			{
				scanf("%d",&a[i][j][0]);
				for(v=1;v<=a[i][j][0];v++)
				{
					scanf("%d",&a[i][j][v]);
				}
			}
			for(j=i+1;j<=n;j++)
			{
				scanf("%d",&a[i][j][0]);
				for(v=1;v<=a[i][j][0];v++)
				{
					scanf("%d",&a[i][j][v]);
				}
			}
		}
		d[1][1]=10000000;
		for(i=2;i<=n;i++)
		{
			if(a[1][i][1]!=0)
			{
				d[1][i]=a[1][i][1];
			}
			else
			{
				d[1][i]=10000000;
			}
		}
		for(i=2;i<=m;i++)
		{
			for(j=1;j<=n;j++)
			{
				d[i][j]=10000000;
				for(u=1;u<j;u++)
				{
					v=((i-1)%a[u][j][0]+1);
					if(a[u][j][v]!=0)
					{
						if(d[i][j]>d[i-1][u]+a[u][j][v])
						{
							d[i][j]=d[i-1][u]+a[u][j][v];
						}
					}
				}
				for(u=j+1;u<=n;u++)
				{
					v=((i-1)%a[u][j][0]+1);
					if(a[u][j][v]!=0)
					{
						if(d[i][j]>d[i-1][u]+a[u][j][v])
						{
							d[i][j]=d[i-1][u]+a[u][j][v];
						}
					}
				}
			}
		}
		printf("Scenario #%d\n",co);
		if(d[m][n]>8000000)
		{
			printf("No flight possible.\n");
		}
		else
		{
			printf("The best flight costs %d.\n",d[m][n]);
		}
		printf("\n");
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=n;j++)
			{
				d[i][j]=0;
			}
		}
		scanf("%d%d",&n,&m);
	}
	return 0;
}

UVA 590-Always on the run（DP）

原文：http://blog.csdn.net/dilemma729/article/details/45345571