Question

你好，有时间请帮忙解答一下这个问题好吗？是关于求最短路径的。

http://zhidao.baidu.com/question/4967186

这里有对问题的详细描述，后边还追加了部分。
http://zhidao.baidu.com/question/496748531.html?quesup2

不好意思，原来的被删除了，这里重新发了一下

Answer 1

可以这样 ： 求最短路可以用三种算法：求任意两个点对间的最短路 : floyd算法 ，求一个点到所有点的最短路径 ： spfa 和 dijkstra
要解决这道题的话 必须会上面三种中的至少一种。如果你是学信息学竞赛的话，我建议你把上面三种都学了，这是基础中的基础。如果是学软件的话，只学dijkstra就可以，但是最好还是学三种

用floyd的话 直接求出所有点对间的最短路 然后你枚举一下这个红点用哪个绿点比较好即可
用spfa的话 在一开始就把所有的绿点加入队列中就可以
dijkstra的话 重复对每一个绿点执行一次算法就可以

可能上面的一些话你还看不懂 所以先学上面的三种算法吧

然后对于记录路径的话， 比如说A点 是从B点 走过来的 那么A点的最短路径就必然是B点的路径后面加上一个A
所以你只需要记录一个 father[] 数组 记录每个点是从哪个点过来的，比如说 father[A] = B
于是我们看到 father 实际就成了一个链表 你要取A的路径的话 遍历一次链表 就可以 了

时间复杂度 ： O(N^3) 空间复杂度 ：O(N^2)

Answer 2

同学，你给的连接是文言文翻译。。。

追问

已经补充了正确连接

Answer 3

锤万凿出深山，烈火焚烧若等闲，粉身碎骨浑不怕，要留清白在人间