社区讨论
萌新最短路求助
P1135奇怪的电梯参与者 8已保存回复 9
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @mi6ydejl
- 此快照首次捕获于
- 2025/11/20 12:50 4 个月前
- 此快照最后确认于
- 2025/11/20 12:50 4 个月前
如题,dij不知道为什么跑不出来
#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 条回复,欢迎继续交流。
正在加载回复...