{"problem":{"name":"[USACO24FEB] Bessla Motors G","description":{"content":"为了推广他的贝斯拉（Bessla）电动拖拉机系列，Farmer John 希望展示贝斯拉的充电网络。他已标记了地图上 $N$（$2\\le N\\le 5\\cdot 10^4$）个编号为 $1\\ldots N$ 的兴趣点，其中前 $C$（$1\\le C<N$）个是充电站，其余为旅游目的地。这些兴趣点之间由 $M$（$1 \\le M \\le 10^5$）条双向道路连接，其中第 $i$ 条连接不同的点 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10193"},"statements":[{"statement_type":"Markdown","content":"为了推广他的贝斯拉（Bessla）电动拖拉机系列，Farmer John 希望展示贝斯拉的充电网络。他已标记了地图上 $N$（$2\\le N\\le 5\\cdot 10^4$）个编号为 $1\\ldots 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$）且长度为 $l_i$ 英里（$1\\le l_i\\le 10^9$）。\n\n贝斯拉一次充电最多可行驶 $2R$英里（$1\\le R\\le 10^9$），使之可以到达一个充电站 $R$ 英里范围内的任何目的地。一个目的地被称之为交通便利的，如果可以从至少 $K$（$1\\le K\\le 10$）个不同的充电站到达目的地。你的任务是帮助 Farmer John 确定交通便利的旅游目的地的集合。 \n\n## Input\n\n输入的第一行包含五个空格分隔的整数 $N$，$M$，$C$，$R$ 和 $K$。以下 $M$ 行，每行包含三个空格分隔的整数 $u_i$，$v_i$ 和 $l_i$，其中 $u_i\\neq v_i$。\n\n充电站的编号为 $1,2,\\ldots,C$。其余兴趣点均为旅游目的地。 \n\n## Output\n\n首先输出一行，包含交通便利的旅游目的地的数量。然后升序输出所有交通便利的旅游目的地，每个一行。\n\n[samples]\n\n## Background\n\n**注意：本题的时间限制为 3 秒，通常限制的 1.5 倍。本题的内存限制为 512MB，通常限制的 2 倍。**\n\n## Note\n\n### 样例解释 1\n\n我们在 $1$ 有一个充电站。从这个充电站出发，我们可以到达 $2$（因为它与 $1$ 的距离为 $3$），但不能到达 $3$（因为它与 $1$ 的距离为 $5$）。因此，只有点 $2$ 是交通便利的。\n\n### 样例解释 2\n\n我们在 $1$ 和 $2$ 有充电站，点 $3$ 和 $4$ 均位于 $1$ 和 $2$ 的 $101$ 距离内。因此，点 $3$ 和 $4$ 都是交通便利的。\n\n### 测试点性质\n\n- 测试点 $4-5$：$K=2$，$N\\le 500$ 且 $M\\le 1000$。\n- 测试点 $6-7$：$K=2$。\n- 测试点 $8-15$：没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10193","tags":["贪心","USACO","2024","O2优化","最短路"],"sample_group":[["3 3 1 4 1\n1 2 3\n1 3 5\n2 3 2","1\n2"],["4 3 2 101 2\n1 2 1\n2 3 100\n1 4 10","2\n3\n4"],["4 3 2 100 2\n1 2 1\n2 3 100\n1 4 10","1\n4\n"]],"created_at":"2026-03-03 11:09:25"}}