Bessla Motors

题目描述

注意：本题时间限制为 3s（默认的 1.5 倍）。内存限制为 512MB（默认的两倍）。 农夫约翰希望通过展示 Bessla 电动拖拉机的充电站网络来推广其 Bessla 电动拖拉机系列。他找到了 $N$（$2\le N\le 5\cdot 10^4$）个兴趣点，编号为 $1\dots N$，其中前 $C$ 个（$1\le C < N$）是充电站，其余的是旅行目的地。这些兴趣点通过 $M$（$1\le M\le 10^5$）条双向道路相互连接，第 $i$ 条道路连接两个不同的兴趣点 $u_i$ 和 $v_i$（$1\le u_i, v_i\le N$），道路长度为 $\ell_i$ 英里（$1\le\ell_i\le 10^9$）。 一辆 Bessla 在一次充电后最多可以行驶 $2R$ 英里（$1\le R\le 10^9$），因此它可以到达距离某个充电站不超过 $R$ 英里的任意目的地。若一个目的地能从至少 $K$（$1\le K\le 10$）个不同的充电站到达，则称该目的地 well-connected 。你的任务是帮助农夫约翰找出所有 well-connected 的旅行目的地集合。

输入格式

第一行包含五个用空格分隔的整数 $N$、$M$、$C$、$R$ 和 $K$。接下来的 $M$ 行中，每行包含三个用空格分隔的整数 $u_i$、$v_i$ 和 $\ell_i$，并满足 $u_i\neq v_i$。 充电站的编号为 $1, 2, \ldots, C$。其余兴趣点均为旅行目的地。

输出格式

首先，在一行中输出 well-connected 的旅行目的地数量。 然后，将所有 well-connected 的旅行目的地按升序输出，每个占一行。

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

1
2

4 3 2 101 2
1 2 1
2 3 100
1 4 10

2
3
4

4 3 2 100 2
1 2 1
2 3 100
1 4 10

1
4

提示

我们有一个位于 $1$ 的充电站。从该充电站出发，我们可以到达点 $2$（因为它与 $1$ 的距离为 $3$），但无法到达点 $3$（因为它与 $1$ 的距离为 $5$）。因此，只有点 $2$ 是 well-connected。 我们在 $1$ 和 $2$ 处有充电站，并且点 $3$ 与点 $4$ 都在 $1$ 和 $2$ 的距离 $101$ 之内。因此，点 $3$ 和点 $4$ 都是 well-connected。 SCORING: 输入 4 和 5：$K = 2$ 且 $N \le 500$ 且 $M\le 1000$。 输入 6 和 7：$K = 2$。 输入 8-15：无额外限制。 题目作者：Alexander Wei

标签: USACO|2024|Gold

来源

USACO|2024|Gold