图论最短路径题目题解

如果我们用普通的Floyd算法和Dijkstra算法来计算，如果评测系统较慢，会有时间超限的风险，这里说了牧场所构成的图是一棵树，我们可以想一个算法针对树这种特殊图。因为最短路径只有一条，所以只要求出两个点共同的祖先就可以了。然后可以发现从开始的点向前遍历，每次遍历这个点的父亲，把遍历到的点标记，标记这个点到原来的点的距离，然后再从结束的点向前遍历，每次遍历这个点的父亲，如果走到了被标记的点就说明找到了第一个共同的祖先，将两个点分别到找到的点距离加起来即可。