欧涛最短路
题号:NC54070
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

已知了飞行器的起点和终点以及n个休息站的坐标,问起点到终点的最短路径是多少?

 

限制:飞行器不能长期飞行,必须中途在某结点下停下休息。(即连续飞行距离应不大于m

欧涛师兄很想在师妹面前大展身手,你能帮助他解决这个问题吗?

输入描述:

第一行输入两个数,整数n和浮点数m

第二行输入六个浮点数x1,y1,z1,x2,y2,z2。分别代表起点坐标(x1,y1,z1)和终点坐标(x2,y2,z2)

紧接着下面n行,每行依次输入三个浮点数,代表休息站的坐标(ai,bi,ci),休息站编码依次为1,2……n。

输出描述:

输出满足条件的起点到终点的最短距离长度(结果保留三位小数)。

依次输出飞行器经过站台的编码(休息站编码为1到n,起点编码Start,终点编码End)

若不能到达终点输出“-1”(无双引号)
示例1

输入

复制
4 5
0 0 0 6 6 0 
-1 1 0
5 6 0
3 4 0 
6 1 0

输出

复制
8.606
Start 3 End

备注:

n<=600