1817. 最短路径

单点时限: 2.0 sec

内存限制: 256 MB

求出有 $n$ $(1 < n < 600)$ 个结点有向图中,结点 $1$ 到结点 $n$ 的最短路径。

输入格式

第一行有 2 个整数 $n,m$ $(0 < m \leq \frac{n(n-1)}{2})$,接下来 $m$ 行每行有三个整数 $u,v,w$ 结点 $u$ 到 $v$ 有一条权为 $w$ 的边 $(w < 10^6)$。

输出格式

输出结点 $1$ 到结点 $n$ 之间的最短路径,如果 $1$ 到 $n$ 之间不存在路径,输出 $-1$。

样例

Input
3 3
1 2 10
2 3 15
1 3 30
Output
25

1288 人解决,1616 人已尝试。

1877 份提交通过,共有 5313 份提交。

1.3 EMB 奖励。

创建: 17 年,1 月前.

修改: 6 年,4 月前.

最后提交: 1 周,4 天前.

来源: 数据结构课程上机实践

题目标签