关于这道题的神奇做法
查看原帖
关于这道题的神奇做法
906916
Contain_Thunder楼主2024/1/27 15:15
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct edge{int next,to,v;} e[200010];
int n,m,s;
int h[200010],ei=0;
int dis[200010],u[200010];
inline void add(int x,int y,int v){ei++,e[ei].v=v,e[ei].to=y,e[ei].next=h[x];h[x]=ei;}
struct node{
    int id,v;
    bool operator <(const node & x) const{return v>x.v;}
};
void dij(int f){
    priority_queue<node>qu;
    node f1;
    memset(dis,0x3f,sizeof(dis));
    f1.id = f,f1.v = 0,dis[f] = 0,qu.push(f1);
    while(!qu.empty()){
        int id=qu.top().id;
        qu.pop();
        if(u[id]==1) continue;      
        u[id]=1;
        for(int i=h[id];i;i=e[i].next){
            int to = e[i].to;
            if(u[to]==1) continue;
            if(dis[to]>dis[id]+e[i].v){
                dis[to] = dis[id]+e[i].v;
                node f2;
                f2.id = to,f2.v = dis[to];
                qu.push(f2);
            }
        }
    }
}
signed main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%lld",&x);
        if(i+x<=n) add(i,i+x,1); 
        if(i-x>=0) add(i,i-x,1); 
    } 
    dij(m);
    if(dis[s]==4557430888798830399){
    	cout<<-1;
    	return 0;
	}
    printf("%lld",dis[s]);
    return 0;
} 
2024/1/27 15:15
加载中...