题解 P3556 【[POI2013]MOR-Tales of seafaring】

· · 题解

给 n 个点 m 条边无向图，每次询问两个点之间是否有长度为 d 的路径（不一定是简单路径）

题目链接

题意分析

注意题目中的 “（不一定是简单路径）”，也就是说可以在一条边重复走多次，也就是可以在两个点之间反复横跳

反复横跳意味着什么，如果从 s (起点)走到 t (终点)如果没有 d 那么长，比 d 要短，可以在最后两个点不断来回重复走，使路径 =d ，但是要注意一点，反复横跳每次都会把路径长度 +2，所以 s 走到 t 的路径必须是和 d 奇偶性相同，我们只需要求出 s 到 t 的奇数最短路径和偶数最短路径即可。

另外要注意这个最短路必须 \leq d。如果连最短路都比 d 长，d 步肯定不能从 s 走到 t 。

CODE:

#include<iostream>
#include<cstdio>
#define re register//卡常技巧 
using namespace std;
int n,m,k;
int hed[20002],next[20002],to[20002],tot;
int dis[10002][10002];
short q[50000001];
int head=1,tail=1;
inline int read()
{
    re int r=0,w=1;
    re char ch=getchar();
    while(ch<'0'||ch>'9')
      {
        if(ch=='-') w=~w+1; 
        ch=getchar();
      }
    while(ch>='0'&&ch<='9')
      {
        r=(r<<3)+(r<<1)+(ch^48);
        ch=getchar();
      }
    return r*w;
}
void add(int x,int y) {
    to[++tot]=y;next[tot]=hed[x];hed[x]=tot;
    to[++tot]=x;next[tot]=hed[y];hed[y]=tot;
    //建x,y的双向边 使用了邻接表 
}
void bfs(int i)
{
    re int x;
    q[1]=i;
    head=1;
    tail=1;
    while(head<=tail) {
        x=q[head];
        head++;//每次处理队头 
        for(int j=hed[x]; j; j=next[j]) {
            if(!dis[i][to[j]]) {//如果当前没被bfs搜到过，因为先被bfs到的一定是最短路 
                dis[i][to[j]]=dis[i][x]+1;//从i到to[j]的最短路可视为从i到x再到to[j]
                //有点像dp或者Floyd的思想，只不过我们这里转移一次就是最优解
                q[++tail]=to[j];//如果搜到就入队 
            }
        }
    }
}
int main() {
    n=read();
    m=read();
    k=read();
    re int x,y;
    for(re int i=1; i<=m; i++) {
        x=read();y=read();
        add(x,y+n);
        add(y,x+n);//建边 
    }
    for(re int i=1;i<=n;i++)
       bfs(i);
    //这里使用了离线处理 
    re int sx,sy,d;
    for(re int i=1; i<=k; i++) {
        sx=read();sy=read();d=read();
        if(d%2==1) if(dis[sx][sy+n]<=d&&dis[sx][sy+n]) {puts("TAK"); continue ;}
        //如果d是奇数，那么查询sx到sy的奇数最短路 
        //如果sx到sy有奇数最短路并且这个最短路<=d就TAK 
        if(d%2==0) if(dis[sx][sy]<=d&&dis[sx][sy]) {puts("TAK"); continue ;}
        //反之，查询sx到sy的偶数最短路 
        //如果sx到sy有偶数最短路并且这个最短路<=d也TAK
        puts("NIE");
        //如果前面都没有输出TAK，这里就输出NIE 
    }
    return 0; 
}