-->
当前位置:首页 > 题库 > 正文内容

编程题:最短路径

Luz2年前 (2022-08-11)题库465
给定一幅 $n(1≤n≤1000)$ 个点 $m(1 \leq m \leq \frac {n(n-1)}{2})$ 条边的有向图,每条边有边权, 表示走过这条边需要花费的时间,我们只能从编号小的点走到编号大的点,问从1号点走到n号点最少要花费多长时间




### 输入格式:

第一行读入两个数$n(1≤n≤1000)
$和$m(1 \leq m \leq \frac {n(n-1)}{2})$,$n$表示有$n$个节点,$m$表示有$m$条边。
接下来$m$行,每行读入三个数$x$,$y$和$z$$(1 \leq x < y \leq n, 1 \leq z \leq 100)$,表示从点$x$有一条耗费时间为$z$的路径,可以到达$y$。数据保证两个点之间最多只有一条边。

### 输出格式:

输出一个数,表示从1号点走到n号点花费的最短时间。

### 输入样例:

在这里给出一组输入。例如:

in
8 10
1 2 1
1 3 2
2 3 5
2 4 3
2 5 4
3 6 4
4 7 2
5 7 1
6 7 3
7 8 2


### 输出样例:

在这里给出相应的输出。例如:

out
8







答案:若无答案欢迎评论

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。