Fixed Length Walk Queries

题目描述

给定一个有 n 个节点和 m 条边的无向图。该图是简单且连通的。 你从一个特定的节点开始，每一步必须沿着一条边移动到另一个节点。 你的任务是回答 q 个查询，形式为：“是否有可能从节点 a 开始在恰好 x 步后到达节点 b？”。

输入格式

第一行包含三个整数 n、m 和 q：节点数、边数和查询数。节点编号为 1,2,$\dots$,n。 随后有 m 行描述边。每行包含两个整数 a 和 b：表示节点 a 与节点 b 之间有一条边。 最后有 q 行，每行描述一个查询。每行包含三个整数 a、b 和 x。

输出格式

对于每个查询，在单独一行上输出答案（YES 或 NO）。

4 5 6
1 2
2 3
1 3
2 4
3 4
1 2 2
1 4 1
1 4 5
2 2 1
2 2 2
3 4 8

YES
NO
YES
NO
YES
YES

提示

$2 \le n \le 2500$ $1 \le m \le 5000$ $1 \le q \le 10^5$ $0 \le x \le 10^9$

标签: CSES3357|高级图论问题

来源

CSES3357|高级图论问题