Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem F: 六队-Utopian’s Maze

Problem F: 六队-Utopian’s Maze

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 9  Solved: 2
[Submit][Status][Web Board]

Description

​ Utopian在玩一个有趣的游戏。在一个巨大的三维虚无空间内,存在n个站立点(编号1-n)。Utopian需要操作他的角色从给定的起点编号s,尝试通过若干的站立点到达要求的终点编号e。

​ Utopian的角色从站立点a到达站立点b必须遵循下列规则:

  1. Utopian对距离的计算遵循欧几里得距离
  2. Utopian的每一步必然选择未到达过的站立点中离当前站立点距离最近的点
  3. Utopian的角色每次移动的最远距离为d

Input

本题包含多组数据

输入的第一行给定一个整数T,表示数据组数。保证

接着依次输入T组数据,每组数据的第一行包含四个整数n,d,s,e。保证

之后的N行,表示第i个站立点的坐标,每行包括三个实数。保证

Output

对于每组数据,试判断根据角色移动规则,能否从s到达t。若不能,请输出Impossible!;若能,请给出S到T的路径,通过站立点编号的形式。

Sample Input

1
5 10 2 5
1 3 5
2 4 6
10 10 10
20 1 3
2 4 10

Sample Output

2 1 5

HINT

[Submit][Status][Web Board]