o2求解
查看原帖
o2求解
169555
Kiloio楼主2021/6/20 20:52

先放代码:

#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不是优化时间吗?

2021/6/20 20:52
加载中...