Art Gallery on Graph

题目描述

有一个包含 $N$ 个顶点和 $M$ 条边的简单无向图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。边 $i$ 连接顶点 $a_i$ 和顶点 $b_i$。
$K$ 名编号为 $1$ 到 $K$ 的警卫驻守在一些顶点上。警卫 $i$ 驻守在顶点 $p_i$ 并且拥有耐力 $h_i$。所有 $p_i$ 都互不相同。 当满足以下条件时，顶点 $v$ 被称为 被守卫的：

存在至少一个警卫 $i$，使得顶点 $v$ 与顶点 $p_i$ 之间的距离不超过 $h_i$。

这里，顶点 $u$ 与顶点 $v$ 之间的距离定义为连接顶点 $u$ 与 $v$ 的路径中边的最小数量。 按升序列出所有被守卫的顶点。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $K$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_M$ $b_M$ $p_1$ $h_1$ $p_2$ $h_2$ $\vdots$ $p_K$ $h_K$

输出格式

按以下格式输出答案。这里，

$G$ 是被守卫的顶点数， $v_1, v_2, \dots, v_G$ 是按升序排列的被守卫的顶点编号。

$G$ $v_1$ $v_2$ $\dots$ $v_G$

5 5 2
1 2
2 3
2 4
3 5
1 5
1 1
5 2

4
1 2 3 5

3 0 1
2 3

1
2

10 10 2
2 1
5 1
6 1
2 4
2 5
2 10
8 5
8 6
9 6
7 9
3 4
8 2

7
1 2 3 5 6 8 9

提示

$1 \leq N \leq 2 \times 10^5$ $0 \leq M \leq \min \left(\frac{N(N-1)}{2}, 2 \times 10^5 \right)$ $1 \leq K \leq N$ $1 \leq a_i, b_i \leq N$ 给定的图是简单图。 $1 \leq p_i \leq N$ 所有 $p_i$ 互不相同。 $1 \leq h_i \leq N$ 所有输入值均为整数。被守卫的顶点是 $1, 2, 3, 5$.
这些顶点被守卫的原因如下。

顶点 $1$ 与 $p_1 = 1$ 之间的距离为 $0$，不大于 $h_1 = 1$。因此，顶点 $1$ 被守卫。 顶点 $2$ 与 $p_1 = 1$ 之间的距离为 $1$，不大于 $h_1 = 1$。因此，顶点 $2$ 被守卫。 顶点 $3$ 与 $p_2 = 5$ 之间的距离为 $1$，不大于 $h_2 = 2$。因此，顶点 $3$ 被守卫。 顶点 $5$ 与 $p_1 = 1$ 之间的距离为 $1$，不大于 $h_1 = 1$。因此，顶点 $5$ 被守卫。
给定的图可能没有任何边。

标签: AtCoder|abc305E

来源

AtCoder|abc305E