心脏不好者勿入
反复横跳
敌袭!!
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
typedef long long LL;
const int N = 100010, M = 2 * N, INF = 0x3f3f3f3f;
int n, m, q;
int dist[N][2];// 源点为 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 ++ ;
}
void spfa() // bfs??
{
memset(dist, 0x3f, sizeof dist); // 初始无穷大, 即无法走到
dist[1][0] = 0; // 1 号点离 1 号点距离为 0 无奇数距离, 距离只有0, 记为偶数距离(0 是偶数)
queue<PII> q;
q.push({1, 0}); // 编号, 奇数距离点/偶数距离点
while (!q.empty())
{
PII t = q.front();
q.pop();
int u = t.first, op = t.second;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j][!op] > dist[u][op] + 1) // 距离加一, 奇偶相反
{
dist[j][!op] = dist[u][op] + 1;
q.push({j, !op});
}
}
}
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
spfa();
while ( q -- )
{
int a, b;
scanf("%d%d", &a, &b);
if(a == 1 && h[1] == -1) puts("No"); // 只有 1 一个点
else if(dist[a][b & 1] <= b) puts("Yes");
// 奇偶性相同的最短路距离小于b
// 则在走到 1 后可以与旁边任意一点"反复横跳"
else puts("No");
}
return 0;
}
/*
1
*/