比赛 NNOI2024 评测结果 AAAAAAAAAA
题目名称 奇怪的电梯 最终得分 100
用户昵称 袁书杰 运行时间 0.033 s
代码语言 C++ 内存使用 3.46 MiB
提交时间 2024-12-28 19:44:33
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct edge {
	int u,v,w,nxt;
} e[10005*2];
int etot,head[10005],dis[10005],n,a,b,k[205];
bool vis[10005];
void adde(int u,int v,int w) {
	e[++etot]= {u,v,w,head[u]};
	head[u]=etot;
}
struct node {
	int u,dis;
	bool operator<(const node&a)const {
		return a.dis<dis;
	}
};
priority_queue<node> q;
void dij(int s) {
	for(int i=0; i<=10000; i++) {
		dis[i]=2147483647;
	}
	q.push(node {s,0});
	dis[s]=0;
	while(!q.empty()) {
		int u=q.top().u;
		q.pop();
		if(vis[u]) {
			continue;
		}
		vis[u]=1;
		for(int i=head[u]; i; i=e[i].nxt) {
			int v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w) {
				dis[v]=dis[u]+w;
				q.push(node {v,dis[v]});
			}
		}
	}
}
signed main() {
	freopen("lift.in","r",stdin);
	freopen("lift.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>a>>b;
	if(a==b){
	    cout<<0;
	    return 0;
    }
	for(int i=1; i<=n; i++) {
		cin>>k[i];
		if(i+k[i]<=n) {
			adde(i,i+k[i],1);
		}
		if(i-k[i]>=0) {
			adde(i,i-k[i],1);
		}
	}
	dij(a);
	if(dis[b]==2147483647) {
		cout<<-1;
	} 
    else {
		cout<<dis[b];
	}
	return 0;
}