/ TYWZ / 题库 /

DFS练习 - 最短路(小规模数据)

DFS练习 - 最短路(小规模数据)

题目描述

给定一个含n个点,m条边的带权有向图,点的编号为1 ~ n,边权均为正整数。用搜索的方法求点s到点t的最短路。

输入格式

第一行是两个正整数:n,m。
之后有m行,每行三个正整数v1,v2,w,表示边v1→v2的权值为w。对于任意两点v1和v2,v1→v2在数据中至多只出现一次,但v1→v2和v2→v1可能共存,且权值未必相同。
最后一行是两个正整数:s,t。

输出格式

如果s→t的路径存在,则输出最短路径长。若不存在则输出-1。

样例

输入

6 8
1 2 5
1 3 6
3 2 2
2 4 9
4 3 3
4 5 8
5 6 3
4 6 4
1 6

输出

18

信息

难度
7
分类
搜索 | 图结构 | 最短路 点击显示
标签
(无)
递交数
48
已通过
9
通过率
19%
上传者