06734. USACO·充电站选址 未做

注意：本题的时间限制为 3 秒，通常限制的 1.5 倍。本题的内存限制为 512MB，通常限制的 2 倍。

为了推广他的贝斯拉（Bessla）电动拖拉机系列，Farmer John 希望展示贝斯拉的充电网络。他已标记了地图上 $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$）。

贝斯拉一次充电最多可行驶 $2R$ 英里（$1\le R\le 10^9$），使之可以到达一个充电站 $R$ 英里范围内的任何目的地。一个目的地被称之为交通便利的，如果可以从至少 $K$（$1\le K\le 10$）个不同的充电站到达目的地。你的任务是帮助 Farmer John 确定交通便利的旅游目的地的集合。

输入的第一行包含五个空格分隔的整数 $N$，$M$，$C$，$R$ 和 $K$。以下 $M$ 行，每行包含三个空格分隔的整数 $u_i$，$v_i$ 和 ${\ell }_i$，其中 $u_i\ne v_i$。

充电站的编号为 $1,2,\dots ,C$。其余兴趣点均为旅游目的地。

首先输出一行，包含交通便利的旅游目的地的数量。然后升序输出所有交通便利的旅游目的地，每个一行。

【样例解释】

• 测试点 6-7：$K=2$。

• 测试点 8-15：没有额外限制。

【数据规模与约定】

• 测试点 4-5：$K=2$，$N\le 500$ 且 $M\le 1000$。

• 测试点 6-7：$K=2$。

• 测试点 8-15：没有额外限制。

供题：Alexander Wei