当前位置:首页 > 图论 > 最短路径 > 正文
SSOJ2433最短路径shopth
1462+

题目大意:给定一个有向图,无负环,有负边,求v点到其他各个点的最短距离是多少?

题目描述

       给出一个有向图G=(V,E)和一个原点v0∈V,请写一个程序输出v0和图G中其他顶点的最短路径。只要所有的有向环权值都是正的,我们就允许图的边为负值。顶点的标号从1到n(n为图G的顶点数)。

输入

第1行:一个正数n(2<=n<=80),表示图G的顶点总数。

第2行:一个整数,表示源点v0(v0∈V,v0可以是图G中任意一个顶点)。

第3至第n+2行,用一个邻接矩阵W给出了这个图。

输出

共包含n-1行,按照顶点的编号从小到大的顺序,每行输出源点v0到一个顶点的最短距离,每行的具体格式参照样例

样例输入

5
1
0 2 - - 10
- 0 3 - 7
- - 0 4 -
- - - 0 5
- - 6 - 0

样例输出

(1->2)=2
(1->3)=5
(1->4)=9
(1->5)=9

提示

样例所对应的图如下:

解题思路

有负边,迪杰斯特拉不能用。用邻接表或者前向星存储边后,SPFA可以快速求出单源最短路径,最后依次输出v到其他各点的最短路径即可。

对于既有数字、又有字符的数据,可以逐个字符读入,如果是连续的数字,则将其转化成数字。当然,也可以尝试用格式化读入,遇到空格回车暂停,每次读入一个可见的字符或者数字,如果读到数字,函数返回值为读到数据的个数,根据返回值可以判断是否存在边。

程序实现

邻接表

前向星

更多
SSOJ2433最短路径shopth:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter