新手天翼
最短路径问题：
给出一个有向图G=(V, E)，和一个源点v0∈V，请写一个程序输出v0和图G中其它顶点的最短路径。只要所有的有向环都是正的，我们就允许图的边有负值。顶点的标号从1到n（n为图G的顶点数）。
输入描述 Input Description
第1行：一个正数n（2<=n<=80），表示图G的顶点总数。
第2行：一个整数，表示源点v0（v0∈V，v0可以是图G中任意一个顶点）。
第3至第n+2行，用一个邻接矩阵W给出了这个图。
输出描述 Output Description
共包含n-1行，按照顶点编号从小到大的顺序，每行输出源点v0到一个顶点的最短距离。
样例输入 Sample Input
5
1 0 2 - -
10 - 0 3 - 7
- - 0 4 -
- - - 0 5
- - 6 - 0
样例输出 Sample Output
(1 -> 2) = 2
(1 -> 3) = 5
(1 -> 4) = 9
(1 -> 5) = 9
数据范围及提示 Data Size & Hint
结果保证在64位二进制整型范围内。
这道题，我先讲一讲图（给萌新讲讲）
邻接矩阵可以这么理解：
对于右图，你可以建一个这样的矩阵：
0 2 3 ∞
∞ 0 1 5
∞ ∞ 0 4
∞ ∞ ∞ 0
现在，第i行第j列的数字就是从i点到j点的长度了。
好，回到题目
对于这题，你会想到那些思路呢？
1.简单递推
对于每一个点，它能到哪，就对它能到的点进行松弛。
什么是松驰呢？
就是把从a到b的距离和从a到c+从c到b的距离比较一下，然后取小者。
比如这一题，我可以建一个数组a[]
第i个数表示v0到i的最短路径长度
一开始，数组为{0,∞,∞,∞}
然后发现1能到2、3
那我要不要通过1再到2呢？
答案是肯定的。数组变为{0,2,∞,∞}
那要不要从1直接到3？
目前没有更快的，变成{0,2,4,∞}
发现对所有边遍历之后，至多遍历n遍，答案就是最优解了。
时间复杂度O(nm)=O(n^3)，不超。
这是啥？这其实是H3的SPFA！
但，这不就是H2的递推吗？
2.贪心
直接使用贪心思想，从v0到哪里最快就先松弛哪里
比如这题，
一开始，数组为{0,∞,∞,∞}
然后发现1能到2、3
那我要不要通过1再到2呢？
答案是肯定的。数组变为{0,2,∞,∞}
那要不要从1直接到3？
目前没有更快的，变成{0,2,4,∞}
好，以后就没有1的事了。
现在到2最快，再松弛,变成{0，2，3，7}
然后在分别对3和4松弛，就变成{0,2,3,6}了。
就这么交的话，WA70，如果是比赛，那也很好了。
但是怎么AC呢？
(下面一句我得划断句符号了）
如果/有的点(如点b)松弛以后/把/从v0到松弛过的点(如点a)的距离/变短了，就/把a标记为未松弛。
好，计算时间复杂度，O（n^2*k(k为负权边数量））<O(n^2*m)=O(n^4),压线。
最后就AC了。
（这不是Dijkstra吗？）
那看看题库
Folyd是啥？
管它是啥！
过了就好！
陈俊霖在2022-10-04 15:11:24追加了内容
板块好像发错了，别举报
