问题陈述
JAG 王国由 $N$ 城市和 $M$ 双向道路组成。第 $i$ 条道路 $(u_i,v_i,c_i)$ 连接城市 $u_i$ 和城市 $v_i$,长度为 $c_i$。 有一天,你,一位 JAG 王国的公民,决定从 $S$ 城市前往 $T$ 城市。 然而,您知道JAG王国的其中一条道路目前正在建设中,您无法通过该道路。 你不知道那是哪条路。只有当您位于道路所连接的任一城市时,您才能知道该道路是否正在建设。
您的任务是在最坏的情况下最小化路线的总长度。您无需在出发前决定路线,可以随时选择下一步要去哪里。
如果在最坏的情况下无法到达城市$T$,则输出 -1.
输入
输入由单个测试用例组成,格式如下。
$N$$M$$S$$T$ $u_1$ $v_1$ $c_1$ $\vdots$ $u_M$ $v_M$ $c_M$
第一行包含四个整数 $N$、$M$、$S$ 和 $T$,其中 $N$ 是城市数量 ($2 \leq N \leq 100{,}000$),$M$ 是双向道路数量 ($1 \leq M \leq 200{,}000$),$S$ 是出发城市 ($1 \le S \le N$),$T$ 是您想要到达的城市 ($1 \le T \le N$, $S \neq T$)。以下$M$行表示道路信息:$M$行中的第$i$行由三个整数$u_i$、$v_i$、$c_i$组成,这意味着第$i$条道路连接城市$u_i$和$v_i$($1\leq u_i, v_i,\leq N$,$u_i\neq v_i$),长度为$c_i$($1\leq c_i \leq 10^9$)。如果没有道路正在建设中,您可以假设所有城市对都是相连的。也就是说,对于所有城市 $x$ 和 $y$,在给定的道路下,至少有一条从城市 $x$ 到城市 $y$ 的路线。还保证不存在多重边,即对于所有 $1 \le i < j \le M$,$\{u_i, v_i\} \neq \{u_j, v_j\}$。
输出
输出最坏情况下路径的最小总长度。如果在最坏的情况下无法到达城市$T$,则输出 -1.
示例输入 1
3 3 1 3 1 2 1 2 3 5 1 3 3
样本输入 1 的输出
6
示例输入 2
4 4 1 4 1 2 1 2 4 1 1 3 1 3 4 1
样本输入 2 的输出
4
示例输入 3
5 4 4 1 1 2 3 2 3 4 3 4 5 4 5 6
样本输入 3 的输出
-1