UVA 590-Always on the run（DP）

UVA 590-Always on the run（DP）

題目大意：有若干城市，有些城市可以到達並且有花費，初始在城市1，要求旅游k天，並且最終在城市n，求是否能達到，若能求最小花費。

用d[i][j]表示第i天在城市j的最小花費，從d[i-1][u]遞推而來，其中u是第i-1天所在的城市。

#include
#include
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;jd[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;
}