P11280 题解

ikunTLE · 2024-11-16 19:23:50 · 题解

题目传送门

题意

在一个无向图上，设 \operatorname{dis}(u,v) 为从 u 到 v 的最短路径长度，判断 \operatorname{dis}(a,r)\le\operatorname{dis}(b,r)。

思路

不难想到暴力解法，对于每次询问都用 bfs 求最短路径长度并判断。在此基础上，由于这是一个无向图，所以 \operatorname{dis}(u,v)=\operatorname{dis}(v,u)。可以在建完图后以 r 为起点做 bfs，预处理 r 到所有点的最短路径长度。时间复杂度 \mathcal{O}(n+m+q)。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e6+10;
int dis[N];
vector<int>vc[N];
queue<int>q;
int main(){
    int n=read(),m=read(),r=read();
    while(m--){
        int u=read(),v=read();
        vc[u].push_back(v);
        vc[v].push_back(u);
    }
    memset(dis,-1,sizeof(dis));
    q.push(r),dis[r]=0;
    while(!q.empty()){
        int u=q.front();
        for(auto i:vc[u])
            if(dis[i]==-1){
                dis[i]=dis[u]+1;
                q.push(i);
            }
        q.pop();
    }
    int T=read();
    printf("I\'m here!\n");
    while(T--){
        int u=read(),v=read();
        printf(dis[u]<=dis[v]?"Terry\n":"Jom\n");
    }
    return 0;
}