CF2014E Rendez-vous de Marian et Robin

在谦卑的相会之举中，喜悦如盛开的花朵般绽放。 分别让心愈加思念。Marian 在市场卖出了最后一件商品的同时，Robin 在 Major Oak 完成了训练。他们迫不及待地想要见面，于是两人都毫不耽搁地出发了。 旅行网络由 $n$ 个顶点组成，编号为 $1$ 到 $n$，以及 $m$ 条边。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，需要 $w_i$ 秒才能通过（所有 $w_i$ 都是偶数）。Marian 从顶点 $1$（市场）出发，Robin 从顶点 $n$（Major Oak）出发。 此外，$n$ 个顶点中有 $h$ 个顶点各有一匹马。Marian 和 Robin 都会骑马，并且上马不需要时间（即 $0$ 秒）。骑马时，行进时间减半。一旦上马，马会持续到旅途结束。两人必须在顶点上相遇（即不能在边上相遇）。任意一方都可以选择在任意顶点等待。 请输出 Robin 和 Marian 最早可以相遇的时间。如果顶点 $1$ 和 $n$ 不连通，则输出 $-1$，表示相会取消。

第一行输入一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例数量。 每个测试用例的第一行包含三个整数 $n$、$m$、$h$（$2 \leq n \leq 2 \times 10^5,\, 1 \leq m \leq 2 \times 10^5,\, 1 \leq h \leq n$）——分别表示顶点数、边数和有马的顶点数。 每个测试用例的第二行包含 $h$ 个互不相同的整数 $a_1, a_2, \ldots, a_h$（$1 \leq a_i \leq n$）——表示有马的顶点编号。 接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$（$1 \leq u_i, v_i \leq n,\, 2 \leq w_i \leq 10^6$）——表示有一条边连接顶点 $u_i$ 和 $v_i$，不骑马通过该边需要 $w_i$ 秒。 没有自环和重边。所有 $w_i$ 都是偶数。 保证所有测试用例中 $n$ 和 $m$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示 Robin 和 Marian 最早可以相遇的时间。如果他们无法相遇，输出 $-1$。

在第一个测试用例中，Marian 从顶点 $1$ 骑马到顶点 $2$，Robin 等待。 在第二个测试用例中，顶点 $1$ 和 $3$ 不连通。 在第三个测试用例中，Marian 和 Robin 都前往顶点 $2$ 相遇。 在第四个测试用例中，Marian 先步行到顶点 $2$，在 $2$ 上马后骑马到顶点 $3$ 与 Robin 相遇。 在第五个测试用例中，Marian 先步行到顶点 $2$，在 $2$ 上马后骑马返回顶点 $1$，再前往顶点 $3$，Robin 等待。 由 ChatGPT 4.1 翻译