14064 - 最短路径

n 个城市,编号从 1 到 n 。给定一张地图,其中包含任意两个城市之间的直接距离(即完全图)。你需要找到从城市 x 出发,到达城市 y 的最短路径长度。你可以经过其他城市作为中转。

输入

第一行包含三个整数 n, x, y ,用空格隔开:

  • n :城市的总数
  • x :起点城市编号
  • y :终点城市编号

接下来 n 行,每行包含 n 个整数,表示邻接矩阵的第 i 行第 j 列元素,代表城市 i 到城市 j 的直接距离。保证:

  • 矩阵对称,即第 i 行第 j 列 = 第 j 行第 i 列。
  • 对角线元素为 0(即城市到自身的距离为 0)。
  • 所有距离均为正整数,且 1 \le \text{距离} \le 10^5

输出

输出一个整数,表示从城市 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 中转更短。

数据范围与约定

  • 2 \le n \le 1000
  • 1 \le x, y \le n ,且 x \ne y
  • 所有边权均为正整数,范围 1 \le w_{ij} \le 10^5
  • 矩阵对称且对角为 0。
时间限制 10 秒
内存限制 128 MB
讨论 统计
上一题 下一题