PTA7-2 星际探险 负权的最短路径与SPFA算法_星球旅行最短路径

我们开着飞船从一个星球飞到另一个星球，我们想找到一条能量消耗最低的路线。

题目中，花费的能量用负数表示，而吸收的能量是正值。这可不好办，因为我们隐隐感觉这是一道最短路径的问题，但是消耗都是负数该怎么办？

那就在输入的时候取反吧，这样消耗成了一个正数，而我们要做的就是使得一条路径消耗加起来最小，就可以套用最短路径算法了。特别注意题目中的“不为永动机”这个细节条件，这就可以理解成不会出现“负回路"， 因为经过取反后，如果我们走了一圈消耗的能量为（-x)，那么就相当于得到了(x)的能量，就造出了永动机。

剩下的就是最基本的带负权重的最短路径算法了，你可以拿Bellman-ford试一下，不过最后你应该会发现最后一点超时；然后就从头调整结构，用上SPFA算法吧。

Bellman-ford算法和SPFA结构上的区别让它们之间的转化挺费劲的：Bellman-ford可以直接关于边进行遍历，可以说是围绕边带出点；而SPFA需要围绕被修改的点，从点带出边。

十一月了，时间过得真快; 好久没出去走走了。