P13638 [NWRRC 2021] Kaleidoscopic Route

Kaleidostan 有 $n$ 个城市，通过 $m$ 条双向道路相连。城市编号从 $1$ 到 $n$。每条道路都有一个整数，称为“色彩度”。 Keanu 想从城市 $1$ 前往城市 $n$。他希望选择一条“最短”路线——即经过道路数最少的路线。在所有最短路线中，他又希望选择一条“万花筒”路线——即这条路线中道路的最大色彩度与最小色彩度之差尽可能大。请你帮助 Keanu 找到这样一条路线。

第一行包含两个整数 $n$ 和 $m$，分别表示城市数和道路数（$2 \le n \le 10^5$，$1 \le m \le 2 \cdot 10^5$）。 接下来的 $m$ 行中，第 $i$ 行包含三个整数 $v_i$、$u_i$ 和 $c_i$，表示第 $i$ 条道路连接城市 $v_i$ 和 $u_i$，且色彩度为 $c_i$（$1 \le v_i, u_i \le n$，$v_i \neq u_i$，$0 \le c_i \le 10^9$）。 任意一对城市之间至多有一条道路。保证任意两个城市之间都可以通过道路互达。

第一行输出一个整数 $k$，表示所需路线经过的道路数。 第二行输出 $k+1$ 个整数 $c_0, c_1, \ldots, c_k$，表示路线经过的城市序列（$1 \le c_i \le n$，$c_0 = 1$，$c_k = n$）。

 在示例测试中，所需路线经过 $3$ 条道路，且其最大色彩度与最小色彩度之差为 $8-2=6$。 由 ChatGPT 4.1 翻译