比赛 |
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;
}