SSOJ2433最短路径shopth
4185+
作者：crxis 发布：2017-09-28 分类：最短路径
题目大意：给定一个有向图，无负环，有负边，求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到其他各点的最短路径即可。
对于既有数字、又有字符的数据，可以逐个字符读入，如果是连续的数字，则将其转化成数字。当然，也可以尝试用格式化读入，遇到空格回车暂停，每次读入一个可见的字符或者数字，如果读到数字，函数返回值为读到数据的个数，根据返回值可以判断是否存在边。
程序实现
邻接表
前向星
