下载掌阅APP，畅读海量书库
立即打开
题目描述（HDU2874）： 由于大部分道路在战争期间已被完全摧毁，所以两个城市之间可能没有路径，也没有环。已知道路状况，想知道任意两个城市之间是否存在路径。若答案是肯定的，则输出它们之间的最短距离。
输入： 输入包含多个测试用例。每个用例的第1行都包含3个整数 n、m、c （2≤ n ≤10000，0≤ m <10000，1≤ c ≤1000000）。 n 表示城市数，编号为1～ n 。接下来的 m 行，每行都包含3个整数 i、j 和 k ，表示城市 i 和城市 j 之间的道路，长度为 k 。最后 c 行，每行都包含 i、j 两个整数，表示查询城市 i 和城市 j 之间的最短距离。
输出： 对每个查询，若两个城市之间没有路径，则输出“Not connected”，否则输出它们之间的最短距离。
题解： 本题的两点之间无环，且有可能不连通，有可能不是一棵树，而是由多棵树组成的森林。因此需要判断是否在同一棵树中，若不在同一棵树中，则输出“Not connected”，否则可以使用求解最近公共祖先的Tarjan算法求解。
（1）根据输入的数据，采用链式前向星存储图。
（2）采用Tarjan算法离线处理所有查询。因为本题的操作对象可能有多棵树，因此需要注意两个问题：①修改Tarjan算法，引入一个root参数，用来判断待查询的两个节点是否在同一棵树中；②对未访问过的节点再次执行Tarjan算法。
（3）将每个查询中两个节点之间的距离都存储在答案数组中。
