记录编号	395299	评测结果	AAAAAAAAAA
题目名称	364.[HDU 1548] 奇怪的电梯	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-04-15 15:27:04	内存使用	0.00 MiB

#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int INF=0x7FFFFFFF;
const int INFI=0x7F7F7F7F;
const int MAXV=210;
const int MAXE=510;

struct Edge{
	int from;
	int to;
	int dis;
	Edge* next;
};

struct HeapNode{
	int node;
	int key;
	bool operator<(const HeapNode& x)const{
		return this->key>x.key;
	}
};

Edge E[MAXE];
Edge* head[MAXV];
Edge* top;

int v;
int s;
int t;
int dis[MAXV];

bool visited[MAXV];

priority_queue<HeapNode> q;

void Initialize();
void Dijkstra();
void Insert(int,int,int);

int Main(){
	Initialize();
	Dijkstra();
	if(dis[t]==INFI)
		puts("-1");
	else
		printf("%d\n",dis[t]);
	return 0;
}

void Dijkstra(){
	int root;
	memset(visited,0,sizeof(visited));
	memset(dis,0x7F,sizeof(dis));
	dis[s]=0;
	q.push(HeapNode({s,0}));
	while(!q.empty()){
		root=q.top().node;
		q.pop();

		if(visited[root])
			continue;
		visited[root]=true;

		for(Edge* i=head[root];i!=NULL;i=i->next){
			if(dis[i->to]>dis[root]+i->dis){
				dis[i->to]=dis[root]+i->dis;
				q.push(HeapNode({i->to,dis[i->to]}));
			}
		}
	}
}

void Initialize(){
#ifndef ASC_LOCAL
	freopen("lift.in","r",stdin);
	freopen("lift.out","w",stdout);
#endif
	int tmp;
	scanf("%d%d%d",&v,&s,&t);
	memset(head,0,sizeof(head));
	top=E;
	for(int i=1;i<=v;i++){
		scanf("%d",&tmp);
		if(i+tmp<=v)
			Insert(i,i+tmp,1);
		if(i>tmp)
			Insert(i,i-tmp,1);
	}
}

inline void Insert(int from,int to,int dis){
	top->to=to;
	top->dis=dis;
	top->from=from;
	top->next=head[from];
	head[from]=top;
	top++;
}

int WORKING=Main();
int main(){;}