如下为我的AC代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ft first
#define sd second
#define mkp make_pair
const ll N=1e5+10,M=2e5+10;
ll n,m,k,s,pr1,pr2,cnt,a,b,c,head[N],f[N],dis[N];
queue<pair<ll,ll> >q;
priority_queue<pair<ll,ll> >p;
struct node{
ll nxt,to,val;
}e[2*M];
void addx(ll u,ll v,ll w){
e[++cnt].nxt=head[u];
e[cnt].to=v;
e[cnt].val=w;
head[u]=cnt;
return ;
}
ll read(){
ll s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x<=9)putchar(x+'0');
else write(x/10),putchar(x%10+'0');
return ;
}
void bfs(){
ll x,y;
while(!q.empty()){
x=q.front().ft;
y=q.front().sd;
q.pop();
if(y>=s)continue;
for(ll i=head[x];i;i=e[i].nxt){
if(f[e[i].to]!=0)continue;
q.push(mkp(e[i].to,y+1));
f[e[i].to]=1;
}
}
return ;
}
void dijstra(ll s){
ll x,v;
for(ll i=1;i<=1e5+5;i++)dis[i]=1e18;
p.push(mkp(0LL,s));
dis[s]=0;
while(!p.empty()){
x=p.top().sd;
p.pop();
for(ll i=head[x];i;i=e[i].nxt){
v=e[i].val;
if(dis[x]+v<dis[e[i].to]){
dis[e[i].to]=dis[x]+v;
p.push(mkp(-dis[e[i].to],e[i].to));
}
}
}
return ;
}
int main()
{
//freopen("P3393_5.in","r",stdin);
//freopen("P3393_5.ans","w",stdout);
n=read(); m=read(); k=read(); s=read();
pr1=read(); pr2=read();
//cout<<pr1<<"!"<<pr2<<endl;
for(ll i=1;i<=k;i++)
{
c=read();
q.push(mkp(c,0));
f[c]=2;
}
for(ll i=1;i<=m;i++){
a=read();
b=read();
addx(a,b,0LL);
addx(b,a,0LL);
}
bfs();
for(ll i=1;i<=cnt;i++){
if(e[i].to==1||e[i].to==n)e[i].val=0;
else if(f[e[i].to]==0)e[i].val=pr1;
else if(f[e[i].to]==1)e[i].val=pr2;
else if(f[e[i].to]==2)e[i].val=2e18;
}
dijstra(1);
write(dis[n]);
return 0;
}
其中bfs到一个点,若已被标记,则不再将其入队。那么有如下问题:如果上一次bfs到这个点并将其标记时,还可向外扩展s1,此次bfs到这个点时,还可向外扩展s2,s1<s2,若不再将其入队,应该会导致一些应被扩展标记的点没有被扩展标记才对,为什么我的程序可以AC?