有 n 个城市,编号从 1 到 n 。给定一张地图,其中包含任意两个城市之间的直接距离(即完全图)。你需要找到从城市 x 出发,到达城市 y 的最短路径长度。你可以经过其他城市作为中转。
第一行包含三个整数 n, x, y ,用空格隔开:
接下来 n 行,每行包含 n 个整数,表示邻接矩阵的第 i 行第 j 列元素,代表城市 i 到城市 j 的直接距离。保证:
输出一个整数,表示从城市 x 到城市 y 的最短路径长度。
5 1 5 0 2 1 3 9 2 0 6 1 3 1 6 0 5 1 3 1 5 0 2 9 3 1 2 0
2
最短路径为 1 -> 3 -> 5,总距离为 ( 1 + 1 = 2 )。直接距离 1 -> 5 为 9,但经过 3 中转更短。