UOJ Logo Zijian Online Judge

ZOJ

#23. 带环最短路(cyclepath)

统计

Ac 来到了一个花园,这个花园有 $n$ 个景点,由于花园客流量太大,景点由 $m$ 条单向带权边相连。

Ac 从 $1$ 号节点开始游览花园,出口在 $n$ 号点,但他不希望过快地离开花园,所以他要求至少走一个环,再走到出口。

请你帮他求出他最短的游览时间(即走过的边权总和,重复经过一条边权值应算多次)。

注意,题面中的环指的是至少包含一条的环。

输入格式

第一行两个正整数 $n$ 和 $m$。

接下来 $m$ 行,每行三个正整数 $u, v, w$,表示一条由 $u$ 指向 $v$ 的权值为 $w$ 的单向边。

输出格式

输出 Ac 最短的游览时间。

如果不能实现,请输出 $−1$。

样例一

input

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

output

7

explanation

选择 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 5 \rightarrow 6$ 这条路径最优。

样例二

见样例数据下载

样例三

见样例数据下载

限制与约定

对于 $20\texttt{%}$ 的数据,$n \le 10,m \le 30$

对于另外 $10\texttt{%}$ 的数据,$n = m$

对于另外 $10\texttt{%}$ 的数据,$m \ge n$ 且前 $n$ 条边中第 $i$ 条边有 $u = v = i, w = 1$

对于另外 $30\texttt{%}$ 的数据,$n, m \le 300$

对于 $100\texttt{%}$ 的数据,$2 \le n, m \le 3000$,$1 \le u, v \le n,1 \le w \le 2 * 10^9$

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

空间限制:$512\texttt{MB}$

下载

样例数据下载