题解：P11280 「GFOI Round 2」Jom & Terry

思路

设

f(x)

为

x

节点到根节点的距离，若

f(x)\ <f(y)

则可以说明

x

节点比

y

节点前往根节点所需要的步数更少，又跟据题中所言：

如果 Terry 先移动到结点 $u$ 后 Jom 在同一回合也移动到 $u$ 是合法的

所以

f(x)\ =f(y)

的时候，则 Terry 和 Jom 在一路上紧追不舍但 Terry 更先到达根节点，而 Jom 紧随其后，此时仍然算 Terry 赢。

而

f(x)\ >f(y)

的时候，则 Jom 比 Terry 提前了至少一个回合到达根节点，所以 Jom 可以一直在根节点不移动然后等到 Terry 在到达与根节点直接相连的边的时候抓到他，此时 Jom 胜利。

解法

通过一遍广度优先搜索来记录

f(x)

的大小，随后通过

O(1)

时间复杂度回答。

总时间复杂度为

O(n+q)

，不加快读快写的话能极限时间过大的数据。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+1e1;
bool vis[maxn];
queue<int > q;
int n,m,root;
int f[maxn];
int t;
vector<int > a[maxn]; 
bool done[maxn];
int main(){
	memset(f,0x3f,sizeof f);
	printf("I'm here!\n");
	scanf("%d%d%d",&n,&m,&root);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		if(u==v) continue;
		a[u].push_back(v);
		a[v].push_back(u);//链接矩阵存双向边
	}
	q.push(root);
	vis[root]=true;
	f[root]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<a[x].size();i++){
			int y=a[x][i];
			if(!vis[y]) q.push(y),f[y]=f[x]+1,vis[y]=true;
		}
	}
	scanf("%d",&t);
	while(t--){
		int x,y;
		scanf("%d%d",&x,&y);
		if(f[x]<=f[y])
			printf("Terry\n");
		else printf("Jom\n");
	}
	return 0;
}

题解：P11280 「GFOI Round 2」Jom & Terry

文章操作

思路

解法

代码

相关推荐

评论

题解：P11280 「GFOI Round 2」Jom & Terry