博客

第一次看这个题想到了BFS，但是上网看了一下解题报告，说BFS会超空间限制，然后就想到用Dijkstra求最短路径了，比较纠结的是记录步数的数组的初始值的设定，最后还是选择了-1，代码如下：

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
	int n,a,b;
	while(cin>>n>>a>>b&&a!=0){
		int k[210]={0},floor[210];
		memset(floor,-1,sizeof(floor));
		for(int i=1;i<=n;i++) cin>>k[i];
		/*下边是dijkstra求最短路径*/
		floor[a]=0;
		bool mark[210];     //标记被探测过的结点
		memset(mark,false,sizeof(mark));
		mark[a]=true;
		int p=a,count=1;    //p表示将要选中的结点，即不属于mark的结点，count计次
		while(p!=b&&count<=n){
			if(p+k[p]<=n&&floor[p+k[p]]==-1) floor[p+k[p]]=floor[p]+1;
			if(p-k[p]>=1&&floor[p-k[p]]==-1) floor[p-k[p]]=floor[p]+1;
			int t=32767;
			for(int i=1;i<=n;i++)
				if(t>floor[i]&&floor[i]!=-1&&!mark[i]) {t=floor[i];p=i;}
			mark[p]=true;
			count++;
		}
		cout<<floor[b]<<endl;
	}
	return 0;
}