Jom and Terry题解

anke2017 · 2024-11-16 15:14:21 · 题解

思路

容易发现，如果 Terry 需要比 Jom 更多的步数才能到达 r 点，那么 Jom 可以堵在 r 点（直接走过去），从而使得 Terry 不能到达 r 点。

但 Terry 需要的步数小于等于 Jom 时呢？

假设 Terry 前往 r 点的最短路径中，第二个节点（即第一步的节点）为 c，那么显然 Jom 不在这个节点上（否则与 Terry 需要步数小于等于 Jom 矛盾），即 Terry 的这一步一定合法。而 Jom 不管怎么走，都无法先移动到 r 或 Terry 的必经节点上（否则也与 Terry 需要步数小于等于 Jom 矛盾），所以 Terry 一定能走到 r。

所以判断 Terry 所在点和 Jom 所在点到 r 的最短距离就行了。最短路径可以用 O(m \log m+q) 的 dijkstra 或 O(n+m+q) 的 BFS。这里选用前者。

代码：

#include<bits/stdc++.h>

using namespace std;

vector<int> e[1000001];
int dij[1000001];
int n,m,r;

struct node
{
    int now,num;
    bool operator <(const node tmp)const
    {
        return num>tmp.num;
    }
};

void dijk()//dijkstra 算法
{
    memset(dij,0x3f,sizeof(dij));
    dij[r]=0;
    priority_queue<node> q;
    q.push({r,0});
    while(!q.empty())
    {
        node tmp=q.top();
        q.pop();
        if(dij[tmp.now]<tmp.num)continue;
        for(int i=0;i<e[tmp.now].size();i++)
        {
            if(dij[e[tmp.now][i]]>dij[tmp.now]+1)dij[e[tmp.now][i]]=dij[tmp.now]+1,q.push({e[tmp.now][i],dij[tmp.now]+1});
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cout<<"I'm here!\n";//签到
    cin>>n>>m>>r;
    for(int i=1;i<=m;i++)
    {
        int t1,t2;cin>>t1>>t2;
        e[t1].emplace_back(t2);
        e[t2].emplace_back(t1);
    }
    dijk();
    int q;cin>>q;
    for(int i=1;i<=q;i++)
    {
        int t1,t2;cin>>t1>>t2;
        if(dij[t1]<=dij[t2])cout<<"Terry\n";//注意小于等于
        else cout<<"Jom\n";
        //cout<<dij[t1]<<' '<<dij[t2]<<'\n';
    }
    return 0;
}