P16273 [蓝桥杯 2026 省 Java B 组] 回程

给定一张包含 $n$ 个点、$m$ 条无向边的图，点的编号为 $1 \sim n$。每条边连接两个不同的点，且可能存在重边。每条无向边由三个整数 $u, v, w$ 描述，表示点 $u$ 与点 $v$ 之间有一条无向边，其代价为 $w$。 你需要从点 $n$ 出发，到达点 $1$。 图中有一个特殊点 $X$。当第一次到达点 $X$ 时，可以获得 **3** 次特殊机会。若 $X = n$，则表示出发时就已经获得这 **3** 次特殊机会。 在之后的行进过程中，每次经过一条边时，都可以选择是否使用一次特殊机会： - 如果不使用，则经过这条边的代价为该边原本的代价 $w$； - 如果使用，则这一次经过该边的代价变为 $1$。 特殊机会可以少用或不用，但总共最多只能使用 **3** 次，每次只能作用于当前经过的一条边。 现在，请你计算从点 $n$ 到点 $1$ 的最小总代价。若无法到达，则输出 $-1$。

第一行包含三个整数 $n, m, X$，分别表示点数、边数和特殊点的位置。 接下来 $m$ 行，每行包含三个整数 $u, v, w$，表示一条连接点 $u$ 与点 $v$ 的无向边，其代价为 $w$。

输出一个整数，表示从点 $n$ 到点 $1$ 的最小总代价。若无法到达，则输出 $-1$。

### 【样例说明】 由于 $X = 6$，而出发点也是 $6$，因此一开始就已经获得了 **3** 次特殊机会。 一种最优走法为：$6 \to 5 \to 4 \to 3 \to 1$，对应边的原代价分别为 $20, 10, 100, 2$。 在其中 **3** 条边上使用特殊机会，例如对代价为 $20, 10, 100$ 的三条边使用，则这三次经过的代价都变为 $1$，最后一条边仍支付原代价 $2$。 因此总代价为 $1 + 1 + 1 + 2 = 5$ ### 【评测用例规模与约定】 对于 $30\%$ 的评测用例，$n, m \leq 500$。 另有额外 $30\%$ 的评测用例，所有边的代价 $w$ 相同。 对于所有的评测用例，$1 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 2 \times 10^5$，$1 \leq w \leq 10^9$，$1 \leq X, u, v \leq n$。 保证图中不含自环，但可能存在重边。