CF852D Exploration plan

Bubble Cup X 的参赛者们在比赛结束后聚在一起，讨论了解东道主国家及其城市的最佳方式。 经过一番对塞尔维亚地图的研究，参赛者们得出了如下事实：国家有 $V$ 个城市，编号从 $1$ 到 $V$，城市之间通过 $E$ 条双向道路相连。每一条道路都有一个权值（通过这条路所需的时间）。Bubble Cup 有 $N$ 支队伍，参赛者们计划如下：每支队伍从 $V$ 个城市中的一个出发，其中部分队伍可能从同一个城市出发。 他们希望找到最短的时间 $T$，使得每支队伍都能在 $T$ 分钟内自由移动，且最终所在的不同城市的数目不少于 $K$（因为他们只有到达的城市才能真正了解）。队伍可以选择不移动，若喜欢某个城市，可以一直待在那里直到时间过去。 请帮参赛者们计算出所需的最短时间 $T$，使得每支队伍最终可以到达至少 $K$ 个不同的城市。如果无论怎么移动都无法满足条件，输出 $-1$。 注意，某些城市之间可能有多条道路。

第一行包含四个整数：$V$、$E$、$N$ 和 $K$，分别表示城市数、道路数、队伍数以及最终需要到达的不同城市最少数量。（$1 \leq V \leq 600,\ 1 \leq E \leq 20000,\ 1 \leq N \leq \min(V,200),\ 1 \leq K \leq N$） 第二行包含 $N$ 个整数，表示每支队伍的起始城市。 接下来 $E$ 行，每行包含 $A_{i}$、$B_{i}$ 和 $T_{i}$，表示有一条道路连接城市 $A_{i}$ 和 $B_{i}$，通过这条道路需要 $T_{i}$ 分钟进行移动。（$1 \leq A_{i},B_{i} \leq V,\ 1 \leq T_{i} \leq 10000$）

输出一个整数，表示所有队伍自由移动后所需的最短时间 $T$，使得最终能到达至少 $K$ 个不同的城市。如果无法实现，请输出 $-1$。 如果有解，答案保证不超过 $1731311$。

例如有三支队伍起点在城市 $5$，两支队伍起点在城市 $2$。如果时间为 3 分钟，一种可行方案是：两支队伍留在城市 $2$，一支留在城市 $5$，其余两支分别移动到城市 $3$ 和城市 $1$。这样共有四个不同的城市被“占领”。 由 ChatGPT 5 翻译