UVa 558

Wormholes

from Volume 7. Graph Algorithms and Implementation Techniques

Description

所谓虫洞就是穿过去，可以回到过去！这种牛逼的东西，大家天马行空开始幻想。输入一张宇宙图，图中某些边权值为负，即为虫洞。输出有木有办法不停穿过某些路，无限回到过去！！！

Solution

求图中权值为负的回路。可以用深搜，经过的位置标记一下，并且计算自己所处的时间，再次到达某点时，看看是否时间是否更早了，就可以无限回到过去了，很容易理解。也可以用Bellman-Ford。因为Bellman-Ford有个性质，某点到某点的路径，最多更新n-1次，可以找到最短路径。因此如果超过n-1次，路径还在更新的话，即可说明可以无限回到过去了。