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

这道题是图论题。

思路

可以想到，如果 Jom 先到“根”，则 Terry 一定会输。所以 Jom 一定会沿着开始点到“根”的最短路走（这样可以尽量的比 Terry 先到“根”，从而抓到 Terry）。而 Terry 为了不被抓到，肯定也要尽量快的到达“根”。所以当：

dis(a) \le dis(b)

时，Jom 能抓住 Terry。

跑一遍最短路，按照上面的规则判断一下即可。

代码

CPP

#include <iostream>
#include <queue>
#include <vector>
#define int long long
using namespace std;

inline int read() {
	int s = 0, w = 1;
	char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) w = ch == '-' ? -1 : 1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) s = s * 10 + ch - '0';
	return s * w;
} // 快读

vector < pair <int, int> > G[1000010];
int N, P, C, Q, f[1000010] = {}, x, y, a, b;
bool vis[1000010];

signed main() {
	puts("I'm here!");
//	cin >> N >> P >> C;
	N = read(), P = read(), C = read();
	for (int i = 1; i <= P; i ++) {
		x = read(), y = read();
		G[x].push_back({1, y}), G[y].push_back({1, x});
	}
// 开始跑最短路
	priority_queue < pair <int, int>, vector < pair <int, int> >,
	greater < pair <int, int> > > que;
	que.push({0, C});
	for (int j = 1; j <= N; j ++) f[j] = 1145141919;
	f[C] = 0;
	while (!que.empty()) {
		int x = que.top().second;
		que.pop();
		if (vis[x]) continue;
		vis[x] = true;
		for (int j = 0; j < (int) G[x].size(); j ++) {
			pair <int, int> v = G[x][j];
			if (f[v.second] >= f[x] + v.first && !vis[v.second]) {
				f[v.second] = f[x] + v.first;
				que.push({f[v.second], v.second});
			}
		}
	}
	
	Q = read();
	while (Q --) {
		a = read(), b = read();
		if (f[a] <= f[b]) puts("Terry");
		else puts("Jom"); // 判断距离
	}
}

最后

本人是第一次写题解 ~~，给个赞再走吧！！！~~

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

文章操作

思路

代码

最后

相关推荐

评论

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