1471 - 最短路径

有n个城市,目标从x出发,到达y城

给定一张地图,给出任意两个城市的直接距离

输入

第一行输入三个数字n、x、y

接着n行n列,第i行第j列表示从城市i到j的直接距离,保证第i行第j列的数字为0,保证城市i到城市j的距离等于城市j到城市i的距离

输出

输出仅一个数字,表示从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

2 \leq n \leq 12

时间限制 3 秒
内存限制 128 MB
讨论 统计
上一题 下一题