卡过了80分,剩下两个点TLE,求优化
查看原帖
卡过了80分,剩下两个点TLE,求优化
289275
Terraria楼主2020/9/13 17:03
#include<bits/stdc++.h>
using namespace std;
vector<int> a[100009];
int visited[100009];
int answer[100009];
int n,m;
inline int read(){//快读
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
    	if(ch=='-')f=-1;
    	ch=getchar();
	}
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}
inline void write(int x){快写
    if(x<0) x=~x+1,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=m;i++){
		int u,v;
		u=read();
		v=read();
		a[u].push_back(v);//存边
	}
	for(int i=1;i<=n;i++){
		answer[i]=i;//先设置为最大能够到达当前结点
		memset(visited,0,sizeof(visited));//第i个点是否被遍历过
		visited[i]=1;
		queue<int> q;
		q.push(i);
		while(!q.empty()){//标准宽搜
			int qian=q.front();
			for(int j=0;j<a[qian].size();j++){
				if(!visited[a[qian][j]]){
					q.push(a[qian][j]);
					visited[a[qian][j]]=1;
					if(a[qian][j]>answer[i]) answer[i]=a[qian][j];
				}
			}
			q.pop();
		}
	}
	for(int i=1;i<=n;i++) write(answer[i]),cout<<" ";
	return 0;
}
2020/9/13 17:03
加载中...