先放代码:
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
struct node{
int x,y,nex;
}e[200005];
long long n,m,ty,a,b,last[200005],tot,dis[N][2],vis[N][2],q[N*2],oe[N];
void add(int x,int y){
tot++;
e[tot].x=x,e[tot].y=y,e[tot].nex=last[x],last[x]=tot;
}
void spfa(){
for(int i=1; i<=n; i++){
dis[i][0]=dis[i][1]=10e10;
}
dis[1][0]=0;
int head=1,tail=1;
q[tail]=1;
while(head<=tail){
int u=q[head],t=oe[head];
head++,vis[u][t]=0;
for(int i=last[u]; i; i=e[i].nex){
int v=e[i].y;
if(dis[v][0]>dis[u][1]+1){
dis[v][0]=dis[u][1]+1;
if(!vis[v][0]){
vis[v][0]=1;
tail++,q[tail]=v,oe[tail]=0;
}
}
if(dis[v][1]>dis[u][0]+1){
dis[v][1]=dis[u][0]+1;
if(!vis[v][1]){
vis[v][1]=1;
tail++,q[tail]=v,oe[tail]=1;
}
}
}
}
return ;
}
int main(){
cin>>n>>m>>ty;
for(int i=1; i<=m; i++){
scanf("%lld%lld",&a,&b);
add(a,b),add(b,a);
}
spfa();
if(last[1]=0){
dis[1][0]=10e10;
}
int uu,ll;
while(ty--){
scanf("%lld%lld",&uu,&ll);
if(ll>=dis[uu][ll%2]){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
}
return 0;
}
为什么我这份代码开o2就能AC,不开就全WA?
o2不是优化时间吗?