AT_abc305_e.[ABC305E] Art Gallery on Graph
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
给定一张 N 个点(编号为 1∼N),M 条边的无向图,保证无重边无自环。现在有 K 个被标记的点,其中第 i 个被标记的点的编号为 pi,任何从 pi 出发经过不超过 hi 条边能到达的点都会被染色(包括 pi 自身)。你需要求出这张图最终有哪些点被染色。
输入格式
第一行分别为 N , M , K 。
接下来 M 行,每行两个正整数 ai,bi ,表示编号为 ai,bi 的点连有一条无向边。
接着 K 行,每行两个整数 pi , hi 表示编号为pi 的点将会从自己出发经过不超过 hi 条边进行染色。
输出格式
第一行一个数字 G,表示被染色的点的个数。
第二行 G 个数字,表示被染色的点,按照从小到大的顺序输出。
输入输出样例
输入#1
5 5 2 1 2 2 3 2 4 3 5 1 5 1 1 5 2
输出#1
4 1 2 3 5
输入#2
3 0 1 2 3
输出#2
1 2
输入#3
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
输出#3
7 1 2 3 5 6 8 9
说明/提示
1≤N≤2×105,0≤M≤2×105,1≤K,ai,bi,pi,hi≤N,pi 互不相同。
保证给定的图无重边,无自环。
输入解题思路,AI测评打分。不知道怎么写?