bzoj#P2985. [Balkan2009] year2012

[Balkan2009] year2012

题目描述

传说 2012-12-21 是世界末日啊!(虽然今天已经是 2012-12-26了……)人们都要逃亡了。到处都是自然灾害,导致地球上只有 nn 个地方可以存活了。其中,我们在 ss 号点,喜马拉雅山在 tt 号点。对于这 nn 个点,我们会用 (Xi,Yi,Zi)(X_{i},Y_{i},Z_{i}) 来描述这些点,而坐标原点则是地球中心。显然,这 nn 个地点是不会靠在一起的,那么我们必须要用飞机来飞行。已知我们所坐的飞机会保持一个恒定的速度 vv,并有一个容量为 cc 的油箱。刚出发时,油箱是满的。而这 nn 个点之中,不是能够两两之间互相飞行的。可以飞的航线只有 mm 条,而每一条所需的油量都不一样(双向航线)。更糟糕的是,不是所有的点都能加油,那么就意味着飞行员每到一个地点,就不得不把油加满!已知两点之间的距离为坐标之间的球面距离(因为是在地球上嘛),而飞行总时间为(总距离 /v/v),那么我们要从 ss 号点飞到 tt 号点至少需要多少时间呢?答案保留 1010 位小数。

【注意事项】 1.     两点之间的距离为最短球面距离,可能有不止一条,但是只有一条有用。 2.     a, b之间的航线可能中途经过c点,但这不代表a和c之间或b和c之间有航线。 3.     起飞,降落,加油等时间都可无视。 4.     若无解,则输出0. 5.     若|你输出的答案-标准答案|<=1e-4,则算正确。

输入格式

第1行四个正数 n,m,v,cn, m, v, c。   接下来 nn 行,每行四个数,X_{i}, Y_{i}, Z_{i}, R_{i},其中 Ri=1R_{i}=1 表示该点可加油,Ri=0R_{i}=0 表示该点不可加油。

接下来 mm 行,每行 33 个正整数,Ak,Bk,CkA_{k}, B_{k}, C_{k},其中 Ak,BkA_{k}, B_{k} 表示第 kk 条航线所连接的两个站点。CkC_{k} 表示该航线所需油量。    最后1行,两个正整数,sstt

输出格式

仅一行,为所需最短时间。若无法到达 tt 号点,则输出 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

数据规模与约定

对于 100%100 \% 的数据,2 leqn1×1032\ leq n\leq 1\times 10^31m1×1041 \leq m \leq 1\times 10^41v1×1031 \leq v \leq 1 \times 10^3,为实数,精度最高为 1×1031\times 10^{-3}1c1×1031 \leq c \leq 1\times 10^3100Xi,Yi,Zi100-100 \leq X_{i},Y_{i},Z_{i} \leq 100,实数,精度最高为 1×10181\times 10^{-18},表示第 ii 个点的坐标,其中数据保证 Xi2+Yi2+Zi2X_{i}^{2}+Y_{i}^{2}+Z_{i}^{2}(即地球半径)为一个恒定的正整数(尽管存在精度差,但是|精度差|110 \leq 1^{-10},因此可认为每个点都严格在地球表面)。并保证,任意航线的长度 1×106\geq 1\times 10^{-6}1可加油的站点数量201\leq {\text 可加油的站点数量}\leq 201地点的编号n1\leq {\text 地点的编号} \leq n1航线所需油量c1\leq {\text 航线所需油量}\leq c