题目描述

给定一张包含 $n$ 个点和 $m$ 条边的无向图，再给定 $q$ 个询问：$a_i,L_i$，判断是否存在一条从 $1$ 号点走到 $a_i$ 号点的恰好经过 $L$ 条边的路径。
$n, m \leq 10^5$
$L \leq 10^9$

BFS 最短路

时间复杂度 $O(n + m + q)$

由于我们可以在某一条边上玩折返跑，因此

只要有从 $1$ 号点出发到 $a$ 距离小于等于 $L$ 且奇偶性与 $L$ 相等的路径

那么就有恰好经过 $L$ 条边抵达 $a$ 号点的方案

定义 $d[j][0]$ 表示经过偶数条边，$d[j][1]$ 为经过奇数条边抵达 $j$ 号的最短距离

用 $bfs$ 跑一遍最短路即可，每个点最多入队两次

y总居然还卡了一手特殊情况
当 $1$ 号点是孤立点时，并没有经过正数条边抵达自己的方法
所以加一个tt >= 1判断 $1$ 号点能否抵达其他点

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010, M = N << 1;

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int q[M], hh = 0, tt = -1;
int d[N][2];

void bfs()
{
    memset(d, 0x3f, sizeof d);
    d[1][0] = 0;

    q[++ tt] = 1;

    while(hh <= tt)
    {
        int u = q[hh ++];

        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];

            if(d[u][0] + 1 < d[j][1])
            {
                d[j][1] = d[u][0] + 1;
                q[++ tt] = j;
            }
            if(d[u][1] + 1 < d[j][0])
            {
                d[j][0] = d[u][1] + 1;
                q[++ tt] = j;
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);

    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);

    while(m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    bfs();

    while(q --)
    {
        int u, k;
        scanf("%d%d", &u, &k);
        if(tt >= 1 and d[u][k & 1] <= k)  puts("Yes");
        else  puts("No");
    }
    return 0;
}