洛谷P1135 奇怪的电梯 bellman_ford算法题解
作者:
当下LYC
,
2024-10-18 16:29:37
,
所有人可见
,
阅读 13
#include <bits/stdc++.h>
using namespace std;
const int N = 2240;
struct node{
int a,b,c;
}sp[N];
int dis[N],u[N],a,b,n;
int main()
{
cin >> n >> a >> b;
int cnt = 1;
for(int i = 1,v ; i <= n ; i++){
cin >> v;
if(i+v<=n) sp[cnt++] = {i,i+v,1};
if(i-v>=1) sp[cnt++] = {i,i-v,1};
}
memset(dis,0x3f,sizeof dis);
dis[a] = 0;
for(int k = 1 ; k <= n; k ++ ){
memcpy(u,dis,sizeof dis);
for(int i = 1 ; i <= cnt ; i++) {
dis[sp[i].b] = min(dis[sp[i].b],u[sp[i].a]+sp[i].c);
}
}
if(dis[b]>=0x3f3f3f3f/2) cout << -1 << endl;
else cout << dis[b] << endl;
return 0;
}