为什么TLE 9个点
查看原帖
为什么TLE 9个点
468872
The_43_Bachelor楼主2024/4/30 09:23
#include<bits/stdc++.h>
using namespace std;
const int N=3e7;
long long cnt,head[N],n,m,p,dis[N],f[N],v[N],t;
bool vis[N];
struct node {
	int from,to,nxt;
} e[N];
void add(int u,int v) {
	cnt++;
	e[cnt].from=u;
	e[cnt].nxt=head[u];
	head[u]=cnt;
	e[cnt].to=v;
}
int find(int x) {
	if(x!=f[x]) {
		f[x]=find(f[x]);
	}
	return f[x];
}
void zbb(int x,int y) {
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy) {
		f[fx]=fy;
	}
}
queue<int> q;
void bfs() {
	while(!q.empty()) {
		int now=q.front();
		q.pop();
		if(v[now]==1) {
			continue;
		}
		v[now]=1;
		t=0;
		for(int i=head[now]; ~i; i=e[i].nxt) {
			int y=e[i].to;
			if(v[y]==0) {
				if(dis[y]>dis[now]+1) {
					dis[y]=dis[now]+1;
					q.push(y);
				}
			}
			if(dis[y]>dis[now]+1) {
				dis[y]=dis[now]+1;
			}
			t++;
			if(t>n) {
				break;
			}
		}
	}
}
bool check(int x) {
	for(int i=1; i<=n; i++) {
		f[i]=i;
		vis[i]=0;
	}
	for(int i=1; i<=n; i++) {
		if(dis[i]<=x) {
			vis[i]=1;
		}
	}
	for(int i=1; i<=n; i++) {
		if(vis[i]==1) {
			for(int j=head[i]; j; j=e[j].nxt) {
				if(i<e[j].to&&vis[e[j].to]==1) {
					int fx=find(i);
					int fy=find(e[j].to);
					if(fx!=fy) {
						f[fx]=fy;
					} else {
						return 1;
					}
				}
			}
		}
	}
	return 0;
}
int main() {
	cin>>n>>m>>p;
	for(int i=1; i<=m; i++) {
		int u,v;
		scanf("%lld%lld",&u,&v);
		add(u,v);
		add(v,u);
	}
	if(m<n) {
		cout<<"Poor D!"<<endl;
		return 0;
	}
	for(int i=1; i<=n; i++) {
		dis[i]=210000000;
		f[i]=i;
		vis[i]=0;
	}
	for(int i=1; i<=p; i++) {
		int x;
		scanf("%lld",&x);
		q.push(x);
		dis[x]=0;
	}
	bfs();
	long long l=-1,r=n+1,u,v,fu,fv,ans=3e7;
	while(l+1<r) {
		int mid=(l+r)>>1;
		if(check(mid)==1) {
			r=mid;
		} else l=mid;
	}
	cout<<r<<endl;
	return 0;
}
2024/4/30 09:23
加载中...