关于bfs的疑问
查看原帖
关于bfs的疑问
786861
zzh_KM楼主2025/2/8 14:45

如下为我的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?

2025/2/8 14:45
加载中...