单源最短路

[编程题]单源最短路

热度指数：12145 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在一个有 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]。
注意数据中可能有重边

算法知识视频讲解

宫水三叶的刷题日记

发表于 2021-09-06 12:48:07

基本分析为了方便，我们约定为点数，为边数。根据题意，首先的数据范围只有，的数据范围为，使用「邻接表」或「邻接矩阵」来存图都可以。存图方式在开始讲解最短路之前，我们先来学习三种「存图」方式。邻接矩阵这是一种使用二维矩阵来进行存图的方式。适用于边数较多的稠密图使用，当边数展开全文

风_N++

发表于 2022-02-10 22:46:30

public class Solution { public int findShortestPath(int n, int m, int[][] gr 展开全文

mlpan

发表于 2021-04-20 09:48:17

最短路径 dfs解法利用一个数组保存点的使用状态，遍历过的设置为true，没遍历的设置为false对每一个点的边进行遍历，依次进行以到达最后一个点作为结束，因为题目只让求到n节点（下标也就是n-1）的最短距离注意：题目有个大坑，就是说可能有重复边，所以在构造边图的时候需要进行一个比较（dp[ed 展开全文

摸鱼学大师

发表于 2021-12-09 20:26:33

题目的主要信息：在一个有 n 个点， m 个边的有向图中，已知每条边长，求出 1 到 n 的最短路径如果 1 无法到 n ，输出 -1 图没有自环，可能有重边方法一：floyd算法具体做法：可以用floyd算法计算任意两个节点之间的最短路径，然后取1-n的即可。用矩阵w表示任意两个节点展开全文

toughD

发表于 2021-06-13 21:52:01

有向图就罢了，重边是什么鬼?解法: dijkstra, 时间复杂度：O(V^2) ```class Solution {public: int findShortestPath(int n, int m, vector<vector<int> >& graph) 展开全文

牛一霸

发表于 2021-08-03 23:02:11

题目：单源最短路径描述：在一个有向无环图中，已知每条边长，求出1到n的最短路径，返回1到n的最短路径值。如果1无法到n，输出-1示例1：输入：5,5,[[1,2,2],[1,4,5],[2,3,3],[3,5,4],[4,5,5]]，返回值：9备注：两个整数n和m,表示图的顶点数和边数。一个二维数组展开全文

Ⅲ_Dc

发表于 2022-10-23 15:41:29

int findShortestPath(int n, int m, vector<vector<int> >& graph) { 展开全文

changed.

发表于 2021-08-13 22:55:30

题意整理：题目以边的形式给出一个有向图，要求找到图中指定两个点（1，n）中的最短路径为了便于后续操作，我们先将给出的边权数组转化为点对之间的距离，对于没有边链接的距离为INT_MAX，对于重边取得较小值。方法一：DFS（超时）核心思想：首先，我们需要从起点1开始，往能够前往的点进行搜索。此处展开全文