传说2012-12-21是世界末日啊!(虽然今天已经是2012-12-26了……)人们都要逃亡了。到处都是自然灾害,导致地球上只有n个地方可以存活了。其中,我们在s号点,喜马拉雅山在t号点。对于这n个点,我们会用(Xi, Yi, Zi)来描述这些点,而坐标原点则是地球中心。显然,这n个地点是不会靠在一起的,那么我们必须要用飞机来飞行。已知我们所坐的飞机会保持一个恒定的速度v,并有一个容量为c的油箱。刚出发时,油箱是满的。而这n个点之中,不是能够两两之间互相飞行的。可以飞的航线只有m条,而每一条所需的油量都不一样(双向航线)。更糟糕的是,不是所有的点都能加油,那么就意味着飞行员每到一个地点,就不得不把油加满!已知两点之间的距离为坐标之间的球面距离(因为是在地球上嘛),而飞行总时间为(总距离/v),那么我们要从s号点飞到t号点至少需要多少时间呢?答案保留10位小数。 【数据范围及保证】 2<=n<=1000,整数,表示地点的数量。 1<=m<=10000,整数,表示可互相飞的航线数量。 1<=v<=1000,实数,精度最高为1e-3,表示飞机的恒定速度。 1<=c<=1000,整数,表示飞机油箱容量。 -100<= Xi, Yi, Zi<=100,实数,精度最高为1e-18,表示第i个点的坐标,其中数据保证Xi2+Yi2+Zi2(即地球半径)为一个恒定的正整数(尽管存在精度差,但是|精度差|<=1e-10,因此可认为每个点都严格在地球表面)。并保证,任意航线的长度>=1e-6. 1<=可加油的站点数量<=20 1<=地点的编号<=n; 1<=航线所需油量<=c 【注意事项】
第1行四个正数n, m, v, c 接下来n行,每行四个数,Xi, Yi, Zi, Ri,其中Ri=1表示该点可加油,Ri=0表示该点不可加油。 接下来m行,每行3个正整数,Ak, Bk, Ck,其中Ak, Bk表示第k条航线所连接的两个站点。Ck表示该航线所需油量。 最后1行,两个正整数,s和t。
仅一行,为所需最短时间。若无法到达t号点,则输出0.
6 9 2.5 9 0.0 5.0 0.0 1 0.0 0.0 -5.0 0 0.0 -5.0 0.0 0 0.0 0.0 5.0 0 3.0 4.0 0.0 0 4.0 3.0 0.0 1 1 2 5 2 3 8 1 4 5 4 3 5 1 5 1 5 6 9 5 2 1 2 6 2 6 4 4 1 3
12.5663706144