首页 > 试题广场 >

最短路径

[编程题]最短路径
  • 热度指数:745 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解

给定的有n个顶点和m条边的有向图中,求出s到t的最短距离。


输入描述:
输入第一行,四个整数n,m,s,t;
接下来m行,每行三个整数a,b,c,表示有条连接a到b的边,长度为c。
注意重边的情况。对于100%的数据,。边权


输出描述:
输出s到t的最短距离,要是s无法到t,则输出-1。
示例1

输入

3 3 1 3
1 3 3
1 2 1
2 3 1

输出

2
头像 myorange
发表于 2020-04-06 12:16:42
无需去重边,链式前向星存图,spfa求两点间最短路 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(Syste 展开全文
头像 Huster水仙
发表于 2023-02-06 00:01:56
Dijkstra算法(优先队列优化) 输入邻接矩阵的边 调用迪杰斯特拉算法:每次选取离源点最近的点作为中介,更新到其余的的距离 #include<iostream> #include<vector> #include<cstring> #include< 展开全文

问题信息

上传者:小小
难度:
6条回答 3372浏览

热门推荐

通过挑战的用户

最短路径