AT_abc305_e.[ABC305E] Art Gallery on Graph

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给定一张 NN 个点(编号为 1N1 \sim N),MM 条边的无向图,保证无重边无自环。现在有 KK 个被标记的点,其中第 ii 个被标记的点的编号为 pip_i,任何从 pip_i 出发经过不超过 hih_i 条边能到达的点都会被染色(包括 pip_i 自身)。你需要求出这张图最终有哪些点被染色。

输入格式

第一行分别为 NN , MM , KK

接下来 MM 行,每行两个正整数 ai,bia_i, b_i ,表示编号为 ai,bia_i, b_i 的点连有一条无向边。

接着 KK 行,每行两个整数 pip_i , hih_i 表示编号为pip_i 的点将会从自己出发经过不超过 hih_i 条边进行染色。

输出格式

第一行一个数字 GG,表示被染色的点的个数。

第二行 GG 个数字,表示被染色的点,按照从小到大的顺序输出。

输入输出样例

  • 输入#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

说明/提示

1N2×1051 \le N \le 2 \times 10^50M2×1050 \le M \le 2 \times 10^51K,ai,bi,pi,hiN1 \le K,a_i,b_i,p_i,h_i \le Npip_i 互不相同。

保证给定的图无重边,无自环。

输入解题思路,AI测评打分。不知道怎么写?

首页