UVa 567

Risk

from Volume 7. Graph Algorithms and Implementation Techniques

Description

一张有20个顶点的图上。依次输入每个点与哪些点直接相连。并且多次询问两点间，最短需要经过几条路才能从一点到达另一点。

Solution

询问数较多，是经典的 Floyd求任意两点间的最短路径长度。利用Floyd解题，初始化领接矩阵的时候要注意，可以将没有直接相连的两点之间定义为一个较大的值。但是要注意，Floyd需要将两数相加，因此这个值不能大于int上限的一半。