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

· · 题解

这道题是图论题。

思路

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

dis(a) \le dis(b)

时，Jom 能抓住 Terry。

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

代码

#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"); // 判断距离
    }
}

最后

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