UOJ Logo Universal Online Judge

UOJ

#563. 【NOI2020】翻修道路

Attachment Statistics

C 国中包含 $n$ 座城市,这些城市通过 $m$ 条双向道路连接。城市从 $1$ 到 $n$ 编号,道路从 $1$ 到 $m$ 编号,$i$ 号道路两端连接着城市 $u_i$ 与城市 $v_i$,它的长度为 $w_i$ 米。经由这些道路,从 C 国中任意一个城市出发,均能到达其他所有城市。

C 国人民喜欢环路旅程,但又不喜欢经过太多条道路,为此 C 国的道路被建造得非常特殊。更具体地,对于一条经过 $l$ 条道路的简单环路(即除起点城市外不经过重复城市的环路),它可以表示为 $c_1 \rightarrow c_2 \rightarrow \cdots \rightarrow c_{l-1} \rightarrow c_l$(其中对于所有 $1 \le i < l$,城市 $c_{i}$ 与城市 $c_{i+1}$ 有道路相连;城市 $c_1$ 与城市 $c_l$ 有道路相连;对于所有 $1 \le i < j \le l$,有 $c_i \neq c_j$),若 $l > 3$,则 C 国的道路将满足下列条件:

  • 存在两个在该环路上不相邻的城市 ,满足两个城市间有道路直接相连。即:存在 $1 \le u < v \le l$,使得 $v-u > 2$,$u$ 和 $v$ 不同时为 $1$ 和 $l$,并且城市 $c_u$ 与城市 $c_v$ 间有道路直接相连。

现在 C 国有了新的翻修计划,需要在城市 $s$ 与城市 $t$ 间寻找一条路径进行翻修。翻修时路径中包含的所有道路将无法通行,为了保障人民的日常生活,C 国希望在翻修这条路径时,经由剩余的道路(即没被包含在翻修路径内的道路)依然能满足:从 C 国中任意一个城市出发,均能到达其他所有城市。

C 国找到了身为工程大师的你,请你帮助 C 国找出一条满足上述要求的翻修路径,并使得这条路径的总长尽量小。

输入格式

第一行两个整数 $n,m$ 分别表示城市个数与道路条数。

接下来 $m$ 行每行三个整数 $u_i,v_i,w_i$,依次表示每条道路的两个端点与它的长度。

数据保证每条道路都一定连接两个不同城市,即 $u_i \neq v_i$。

最后一行两个整数 $s,t$,分别表示需要翻修的路径的两个端点。

输出格式

仅一行一个整数,表示满足题目要求的情况下,翻修路径的总长的最小值。

如果不存在满足题目要求的路径,输出一行一个整数 -1

样例一

input

4 5
1 2 1
2 3 1
3 4 1
1 3 5
2 4 6
1 4

output

6

explanation

路径 $(1,2,1),(2,3,1),(3,4,1)$ 是城市 $1$ 和城市 $4$ 间总长最小的路径,但不符合要求。

路径 $(1,3,5),(3,4,1)$ 符合要求,长度为 $6$。

路径 $(1,2,1),(2,4,6)$ 符合要求,长度为 $7$。

除上述两条路径外,没有其他满足要求的路径。

样例二

input

2 1
1 2 1
1 2

output

-1

样例三

见样例数据下载。

该样例与测试点$1 \sim 6$限制相同。

样例四

见样例数据下载。

该样例与测试点$7 \sim 10$限制相同。

样例五

见样例数据下载。

该样例与测试点$11 \sim 15$限制相同。

样例六

见样例数据下载。

该样例与测试点$16 \sim 20$限制相同。

数据范围

对于所有测试点:$2 \le n \le 5 \times 10^5,1 \le m \le 10^6,s \neq t$。

$1 \le u_i,v_i \le n$,$u_i \neq v_i$,$1 \le w_i \le 10^9$,保证任意两条道路它们的端点不全相同。

保证给出的道路满足题面描述第二段中的性质。

每个测试点的具体限制见下表:

测试点编号$n \le$$m \le$特殊限制
$1 \sim 6$$2000$$4000$
$7 \sim 10$$5 \times 10^5$$10^6$A
$11 \sim 15$B
$16 \sim 20$

特殊限制 A:所有道路的长度均相等。

特殊限制 B:所有 $w_i=1$ 的道路恰好构成 $s$ 到 $t$ 的一条路径,且其他 $w_i \neq 1$ 的道路的两条端点在这条路径上距离为 $2$。

时间限制:$6\texttt{s}$

空间限制:$1\texttt{GB}$

下载

样例数据下载

题解

这篇论文中的算法可以用来解决本题。