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了，可以的话，请您参考添加页面，与大家一起分享你的题解！