hdu 1548 a strange lift 迪傑斯特拉 最短路問題

之前活生生地了解錯了，這個電梯是在第幾層時都有相應的移動步數，我了解成了按它的順序（3 3 1 2 5）每次一定要移動這個次序。其他的要考慮起始點和終點相同的情況，即輸出0，而不是-1，要做到這個，在djs()中給儲存起點到各個點的距離的數組d[s]=0就行了，s表示起點下标。是個熟悉迪傑斯特拉的不錯的題。

傳送門：

http://acm.hdu.edu.cn/showproblem.php?pid=1548

#include<stdio.h>
#include<string.h>
#define MAX 205
#define inf 999999
int map[MAX][MAX],vis[MAX],d[MAX];
int n;	
void djs(int s,int e)
{
	int i,j,min,index;
	vis[s]=1;
	for(i=1;i<=n;i++)
		d[i]=map[s][i];
	d[s]=0;
	for(i=1;i<n;i++)
	{
		min=inf;
		for(j=1;j<=n;j++)
		{
			if(vis[j]==0&&d[j]<min)
			{
				min=d[j];
				index=j;
			}
		}
		if(min==inf)
			break;
		vis[index]=1; 
		for(j=1;j<=n;j++)
		{
			if(vis[j]==0&&((d[index]+map[index][j])<d[j]))
			{
				d[j]=d[index]+map[index][j];
			}
		}
	}
	if(d[e]!=inf)
		printf("%d\n",d[e]);
	else
		printf("-1\n");
}
int main()
{
	int i,j,s,e;
	while(scanf("%d",&n)!=EOF,n!=0)
	{
		scanf("%d %d",&s,&e);
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				map[i][j]=inf;
		memset(vis,0,sizeof(vis));
		for(i=1;i<=n;i++)
		{
			int t;
			scanf("%d",&t);
			if(t+i<=n)
				map[i][i+t]=1;
			if(i-t>=1)
				map[i][i-t]=1;	
		}
		djs(s,e);
	}
	return 0;
}