Skip to content

1210: 最短路径

题目

题目描述

终于到了最短路径部分的内容,想必你已经很累了。但还是请坚持,胜利就在前方。

如果你没有去听课,或者是觉得“最短路径”这个名字很陌生,那么请先返回376页,把概念先扫一遍(书上的介绍流程:无权图(搜索)->加权图(dijkstra单源的)->带负权的图(spfa算法)->floyd算法(多源))在这一题中,我们要求实现带负权的单源最短路径算法。由于带负权,dijkstra算法边不能再使用(原因请看P387),所以我们要求利用邻接表,通过搜索算法完成(事实上解决这个问题的最好算法是SPFA算法,P387有它的介绍。如果你有兴趣,当然也可以用它。)。

给定带负权的有向图,起点start,终点end,请计算由start到end的最短路径(数据保证不出现负环)

请不要使用floyd算法。

为简化题目,我们约定:用正整数1,2,3……n来表示每个结点的ID(编号)

输入格式

第1行:n m start end //正整数n ,代表图中结点的数量。非负整数m代表要图中有向边的数量。

第2行到第1+m行: a b p //每行两个整数:代表结点a到结点b有一条有向边(a->b),权值为p

输出格式

一个整数,由start到end的最短路径上边的总权值的大小。

样例输入

7 12 3 6

1 2 2

3 1 4

1 4 1

2 4 3

4 5 2

2 5 10

3 6 3

4 6 -8

4 7 4

5 7 6

7 6 1

1 3 5

样例输出

-3

数据范围

0<n<=10 0<=m<=100

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!