2390: Luffy
内存限制:64 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:3
解决:1
题目描述
平面内给出n个点,记横坐标最小的点为A,最大的点为B,现在要求在每个点经过一次(A点两次)的情况下从A走到B,再回到A的最短路径。 限制条件为:
1. 从A走到B时,只能由横坐标小的点走到大的点。
2. 由B回到A时,只能由横坐标大的点走到小的点。
3. 有两个特殊点b1和b2, b1在0到n-1的路上,b2在n-1到0的路上。
输入
第一行三个整数n,b1,b2,(4 <= n <= 100, 0 < b1,b2 < n-1 且 b1 <> b2)。n表示点数,从0到n-1编号,b1和b2为两个特殊点的编号。 以下n行,每行两个整数x、y表示该点的坐标(0 <= x,y <= 2000),从0号点顺序给出,且x为增序。
输出
第一行输出最短路径长度(精确到小数点后面2位);第二行输出该路径,每两个数之间有且仅有1个空格。保证答案唯一。
样例输入 复制
5 1 3
1 3
3 4
4 1
7 5
8 3
样例输出 复制
18.18
0 1 4 3 2 0