P3556

MikeC · 2021-08-17 13:17:18 · 题解

分析

给定的图是无向图，边权都为一，且不一定是简单路径，故可以在两点间反复横跳。故我们可以采用拆点的方法，将每个点拆成奇数点（即一条长度为奇数的路径的端点）和偶数点（即一条长度为偶数的路径的端点）。由于边权一定，故通过广度优先搜索得到的路径一定是两点间的最短路径。于是我们得到了这样一种解题方案：

• 首先，拆点建边。
• 然后，以每个点为起点进行搜索。
• 最后，离线回答询问。

注意当最短路长度 dis \gt d 时不可能在 s 和 t 间存在一条长度为 d 的路径，需要在回答询问时进行判断。

时间复杂度 O(n^2)。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
struct egde{
    int next;
    int to;
}e[20001];
int head[20001],cnt;
void add(int from,int to){
    e[++cnt].to=to;
    e[cnt].next=head[from];
    head[from]=cnt;
}
int dis[5001][5001];
void bfs(int s){
    queue<int> q;
    q.push(s);
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].next){
            int to=e[i].to;
            if(!dis[s][to]){
                dis[s][to]=dis[s][x]+1;
                q.push(to);
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v+n),add(v+n,u);
        add(v,u+n),add(u+n,v);
    }
    for(int i=1;i<=n;i++)bfs(i);
    for(int i=1;i<=k;i++){
        int s,t,d;
        scanf("%d%d%d",&s,&t,&d);
        if(d%2==1){
            if(dis[s][t+n]<=d&&dis[s][t+n])printf("TAK\n");
            else printf("NIE\n");
        }else{
            if(dis[s][t]<=d&&dis[s][t])printf("TAK\n");
            else printf("NIE\n");
        }
    }
    return 0;
}