首页 > 试题广场 >

单源最短路

[编程题]单源最短路

在一个有 n 个点， m 个边的有向图中，已知每条边长，求出 1 到 n 的最短路径，返回 1 到 n 的最短路径值。如果 1 无法到 n ，输出 -1

图中可能有重边，无自环。

数据范围： $1 < n \le 500$ ， $1 \le m \le 5000$ ， $1 \le dist(n, m) \le 1000$

示例1

输入

5,5,[[1,2,2],[1,4,5],[2,3,3],[3,5,4],[4,5,5]]

示例2

2,1,[[1,2,4]]

两个整数n和m,表示图的顶点数和边数。
一个二维数组，一维3个数据，表示顶点到另外一个顶点的边长度是多少
每条边的长度范围[0,1000]。
注意数据中可能有重边

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

图

上传者：牛客301499号

难度：

0条回答 147收藏 4062浏览

查看代码

扫一扫，把题目装进口袋