社区讨论

萌新最短路求助

P1135奇怪的电梯参与者 8已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@mi6ydejl
此快照首次捕获于
2025/11/20 12:50
4 个月前
此快照最后确认于
2025/11/20 12:50
4 个月前
查看原帖
如题,dij不知道为什么跑不出来
代码略丑
CPP
#include<bits/stdc++.h>
using namespace std;
int cnt,ans,dis[10000],vis[100000],n,a,b,head[1000000];
struct xing{
    int next,to,w;
};
priority_queue< pair<int,int> >q;
xing xx[100000];
void spfa()
{
    dis[a]=0;
    vis[a]=1;
    q.push(make_pair(0,a));
    while(!q.empty())
    {
        int now=q.top().second;
        q.pop();
        if(vis[now]==1)continue;
            vis[now]=1;
        for(int i=head[now];i;i=xx[i].next)
        {
            
            int v=xx[i].to;
            if(dis[v]>dis[now]+xx[i].w)
              {
                  dis[v]=dis[now]+xx[i].w;
                  q.push(make_pair(-dis[v],v));
              }
        }
    }
}
int main()
 {
     memset(dis,2147483647,sizeof(dis));
     cin>>n>>a>>b;
     for(int i=1,j;i<=n;i++)
     {
         cin>>j;
         xx[++cnt].to=i+j;
         xx[cnt].next=head[i];
         xx[cnt].w=1;
         head[i]=cnt;
         if(i-j>0)
         {
             xx[++cnt].to=i-j;
             xx[cnt].next=head[i];
             xx[cnt].w=1;
             head[i]=cnt;
         }
     }
     spfa();
     if(dis[b]==2147483647)cout<<-1;
       else cout<<dis[b];
 }

回复

9 条回复,欢迎继续交流。

正在加载回复...