HDU-1548-奇怪的电梯

这题的题意就是，如果在k层，该数的序号为k，则在k层上只能去k+a[k]层或者k-a[k]，这样的话，就变成了一个单向联通图，对这个Dijkstra算法就可以了。

#include <cstdio>

#include <string.h>

const int INF=1<<30;

int d[210],w[210][210];

bool vis[200];

int n,k,s,e;

void Dijkstra(int s,int e)

{

	int min,x;

	memset(vis,0,sizeof(vis));

	for (int i=0;i<n;i++)

		d[i]=w[s][i];

	d[s]=0;

	vis[s]=1;

	for (int k=1;k<n;k++) {

		min=INF;

		for (int j=0;j<n;j++) {

			if (!vis[j]&&d[j]<min) {

				min=d[j];

				x=j;

			}

		}

		if (min==INF)

			break;

		vis[x]=1;

		for (int i=0;i<n;i++) {

			if (!vis[i]&&d[i]>w[x][i]+d[x])

				d[i]=w[x][i]+d[x];

		}

	}

}

int main()

{

	while (scanf("%d",&n)&&n) {

		scanf("%d%d",&s,&e);

		s--;

		e--;

		for (int i=0;i<n;i++) {

			for (int j=0;j<n;j++)

				w[i][j]=INF;

		}

		for (int i=0;i<n;i++) {

			scanf("%d",&k);

			if (i+k<n)

				w[i][i+k]=1;

			if (i-k>=0)

				w[i][i-k]=1;

		}

		Dijkstra(s,e);

		printf("%d\n",d[e]==INF?-1:d[e]);

	}

	return 0;

}

巴特西

HDU-1548-奇怪的电梯

最新文章

热门文章