来自蒟蒻的呼救声 55pnts WA
查看原帖
来自蒟蒻的呼救声 55pnts WA
514936
EllinY楼主2022/12/22 20:39

求助。。。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PII pair<ll,ll>
vector<ll> go[200001];
ll n,m,q,l,dis1[200001],dis2[200001];//一个是奇数条边最短路,另一个是偶数
priority_queue<PII,vector<PII>,greater<PII> > q1,q2;
bool vis[200001];
void d(ll s){
	dis2[s]=0;
	PII t;
	t.first=0,t.second=s;
	q2.push(t);
	for(ll i=0;i<go[1].size();i++){
		dis1[go[1][i]]=1;
		t.second=go[1][i],t.first=1;
		q1.push(t);
	}
	while(!q1.empty()&&!q2.empty()){
		t=q1.top();
		q1.pop();
		ll p1=t.second;
		for(ll i=0;i<go[p1].size();i++){
			if(dis2[go[p1][i]]>dis1[p1]+1){
				dis2[go[p1][i]]=dis1[p1]+1;
				t.second=go[p1][i],t.first=dis2[go[p1][i]];
				q2.push(t);
			}
		}
		t=q2.top();
		q2.pop();
		ll p2=t.second;
		for(ll i=0;i<go[p2].size();i++){
			if(dis1[go[p2][i]]>dis2[p2]+1){
				dis1[go[p2][i]]=dis2[p2]+1;
				t.second=go[p2][i],t.first=dis1[go[p2][i]];
				q1.push(t);
			}
		}
	}
}//最短路
int main(){
	cin>>n>>m>>q;
	for(ll i=1;i<=m;i++){
		ll a,b;
		cin>>a>>b;
		go[a].push_back(b);
		go[b].push_back(a);
	}
	memset(dis1,0x3f,sizeof(dis1));
	memset(dis2,0x3f,sizeof(dis2));
	d(1);
	while(q--){
		ll a;
		cin>>a>>l;
		if(l%2==1&&dis1[a]<=l||l%2==0&&dis2[a]<=l) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
} 

Thanks♪(・ω・)ノ

2022/12/22 20:39
加载中...