P11321 [NOISG 2020 Qualification] Relay Marathon

Nilan 是 Berapur 国家的一位马拉松组织者。他计划在国家内的城市网络中组织一场接力马拉松。

该国家共有 $N$ 个城市，通过 $M$ 条双向道路连接。每个城市编号为 $1$ 到 $N$，每条道路编号为 $1$ 到 $M$，第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，通行时间为 $w_i$ 秒。道路网络中没有自环或重复边。 在 $N$ 个城市中，有 $K$ 个特殊城市，编号分别为 $A_1, A_2, \dots, A_K$。 接力马拉松的规则如下： 1. 两组人分别从两个起始城市 `start1` 和 `start2` 出发； 2. 第一组人从 `start1` 前往 `finish1`； 3. 第一组人到达 `finish1` 后，第二组人立即（无延迟）从 `start2` 前往 `finish2`； 4. 接力马拉松在第二组人到达 `finish2` 时结束。 接力马拉松的有效条件： - `start1`、`finish1`、`start2` 和 `finish2` 必须是四个不同的特殊城市。 令 $D(a, b)$ 表示从城市 $a$ 到城市 $b$ 的最短通行时间。如果 $a$ 和 $b$ 之间无路径，则定义 $D(a, b) = \infty$。 接力马拉松的总耗时定义为： $$ D(start1, finish1) + D(start2, finish2) $$ 你的任务是找到所有有效的起点和终点组合中，总耗时的最小值。

- 第一行包含三个整数 $N, M, K$，分别表示城市数量、道路数量和特殊城市数量。 - 接下来 $M$ 行，每行包含三个整数 $u_i, v_i, w_i$，表示城市 $u_i$ 和 $v_i$ 之间有一条通行时间为 $w_i$ 秒的道路。 - 最后一行包含 $K$ 个整数 $A_1, A_2, \dots, A_K$，表示特殊城市的编号。

输出一个整数，表示接力马拉松的最小总耗时。

【样例解释】 对于样例 #1： - 有效组合为 `start1 = 1, finish1 = 2, start2 = 3, finish2 = 5`； - $D(1, 2) = 1$，$D(3, 5) = 7$； - 总耗时为 $1 + 7 = 8$。 对于样例 #2： - 有效组合为 `start1 = 1, finish1 = 4, start2 = 5, finish2 = 6`； - $D(1, 4) = 12$，$D(5, 6) = 3$； - 总耗时为 $12 + 3 = 15$。 【数据范围】 - $4 \leq K \leq N \leq 10^5$ - $2 \leq M \leq \min \left( \frac{N(N-1)}{2}, 3 \times 10^6 \right)$ - $1 \leq w_i \leq 1000$ - $1 \leq u_i \neq v_i \leq N$ | 子任务编号 | 分值 | 限制条件 | |:--------:|:---------:|:-------------------------:| | $1$ | $5$ | $4 \leq K \leq N \leq 50$ | | $2$ | $12$ | $4 \leq K \leq N \leq 500$ | | $3$ | $25$ | 城市 $1$ 和城市 $2$ 是特殊城市，直接由一条耗时为 $1$ 秒的道路相连，且城市 $1$ 不与其他城市相连，城市 $2$ 也不与其他城市相连 | | $4$ | $58$ | 无额外限制 |