← 返回题单
题单练习 最短路
← 上一题 下一题 →

A6182 | Roadblocks G

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

Bessie 搬到了一个小农场，有时喜欢回去拜访她的一个好朋友。她不想太快到达她的旧家，因为她喜欢沿途的风景。她决定选择第二短的路径而不是最短的路径。她知道一定存在某条第二短路径。

乡村由 $R(1\le R\le100,000)$ 条双向道路组成，每条道路连接 $N(1\le N\le5000)$ 个交叉路口中的两个，这些交叉路口被方便地编号为 $1$ 到 $N$。Bessie 从交叉路口 $1$ 出发，她的朋友（目的地）在交叉路口 $N$。

第二短路径可以与任何最短路径共享道路，并且可以回溯，即多次使用相同的道路或交叉路口。第二短路径是长度比最短路径长的最短路径（即，如果存在两条或多条最短路径，第二短路径是长度比这些路径长但不比任何其他路径长的路径）。

输入格式

第 $1$ 行：两个用空格分隔的整数：$N$ 和 $R$。


第 $2$ 行到第 $R+1$ 行：每行包含三个用空格分隔的整数：$A$、$B$ 和 $D$，描述连接交叉路口 $A$ 和 $B$ 的一条长度为 $D(1\le D\le5000)$ 的道路。

输出格式

第 $1$ 行：节点 $1$ 和节点 $N$ 之间第二短路径的长度。

输入输出样例

输入 #1
4 4
1 2 100
2 4 200
2 3 250
3 4 100
输出 #1
450
C++ 编辑器
输入
输出