7080번 - A New Beginning 스페셜 저지다국어

An extreme solar eruption has heated the Earth, causing a monstrous cataclysm. Tectonic plates are floating freely along the Earth’s mantle; earthquakes with unseen magnitudes are causing metropolises to collapse to the ground; mountains are inundated by gigantic tsunamis; countries are turning to oceans of lava and volcanic dust.

It’s 21 December 2012 and your only chance to save yourself and your family from the apocalypse is to reach the government ships in the Himalayas – the modern arks that will save mankind. You have an airplane that flies with constant speed and a map with all standing airports. Unfortunately, not all pairs of airports are connected – enormous clouds of volcanic dust are blocking some of the routes, while other airports are too far away from each other. Furthermore, not all airports have fuel available – some of them have nothing left but the naked roads – and there you can’t refuel the aircraft. And since all means of navigation are destroyed, the only possible path between two airports is the shortest one. And on top of all, due to atmospheric instability and dramatic changes of air density, the fuel efficiency of the engines varies between flights. Thus the fuel consumption is also different. The good new is that you know between which airports it is possible to fly and the amount of fuel it would cost, and also where you can refuel. All you have to do is find a way to get from your airport to the airport in the Himalayas as fast as possible. Write a program that computes the minimum amount of time required to achieve that task, given the coordinates of each airport and whether it has fuel, the fuel tank capacity of the airplane, the speed of the airplane, which pairs of airports are connected by a potential flight and how much fuel does each flight require. 

The first line of the standard input consists of four integers: N, M, V and C – the number of airports, the number of pairs of connected airports, the constant speed of the aircraft and the fuel tank capacity, respectively. The next N lines give information about airports. Airports are represented by points in 3-dimensional space and all of them lie on the surface of the Earth whose center is at the origin - (0,0,0). The i-th of these lines consists of three real numbers and a Boolean: X_i, Y_i, Z_i and R_i – the coordinates of the i-th airport and whether you can refuel in it (R_i = 1 means you can, R_i = 0 means you can’t). The next M lines give information about potential flights. Each pair of connected airports is unordered, i.e. a flight from A to B has the same properties as a flight from B to A. The k-th of these lines consists of three integers: A_k, B_k and F_k, denoting a potential flight from airport A_k to airport B_k (consequently from B_k to A_k as well) that requires an amount of fuel equal to F_k (in either direction). The last line consists of integers S and T – the first and the last airport in your route. 

The only line of the standard output must be one real number representing the minimum time required to get from airport S to airport T. An answer is considered correct if it differs from the author’s by no more than 10^-4. If a route cannot be found and you are doomed, just print 0 (zero on one line). 

• 2 ≤ N ≤ 1000 – number of airports. Integer.
• 1 ≤ M ≤ 10000 – number of possible flights. Integer.
• 1 ≤ V ≤ 1000 – airplane’s constant speed. Real number with up to 3 digits to the right of the decimal point.
• 1 ≤ C ≤ 1000 – fuel tank capacity of airplane. Integer.
• -100 ≤ X_i, Y_i, Z_i ≤ 100 – coordinates of i-th airport. Real numbers with up to 18 digits to the right of the decimal point. Besides, X_i² + Y_i² + Z_i² is constant for all i, i.e. all airports will be the same distance from the Earth’s center in a given test case.
• 1 ≤ (number of airports where you can refuel) ≤ 20
• (The Earth’s radius) ≥ 1. Integer. 
• 1 ≤ A_k, B_k ≤ N – airports in k-th potential flight. Different integers. Each (unordered) pair will appear at most once in the input.
• 1 ≤ F_k ≤ C – amount of fuel used up by the airplane in k-th potential flight. Integer. Notes
• A direct route (flight) between two airports is the shortest arc on the sphere representing the Earth’s surface that connects them. Even if there is more than one such arc, it is only the distance that matters.
• No potential flight will be shorter than 10^-6.
• Due to precision errors, the distance from the Earth’s center could slightly differ for different airports. However, the absolute difference between the distance and the Earth’s radius will be no more than 10^-10 and thus the correctness of an algorithm won’t be affected in any way if all airports are considered to be lying strictly on Earth’s surface.
• R_s = 1, i.e. the fuel tank of the airplane is always full in the beginning. Also, each time an airport with fuel is visited, the tank is again filled up.
• The time required for landing, refueling, flying off and accelerating is negligibly small and is considered 0 (zero).
• Potential flights between airports are completely independent. If the arc representing a flight from A to B happens to pass through C, this doesn’t mean that there’s a potential flight between A and C, nor between B

Earth’s radius is 5. The airplane’s speed is 2.5 and the fuel tank capacity is 9. We want to get from 1 to 3. In the picture, potential flights are represented by black arcs, airport numbers are inside the squares and fuel consumption is noted beside the corresponding arcs. Points where we can refuel have a white dot in the middle. Obviously, we can’t simply use the direct routes 1-2-3 and 1-4-3: their fuel consumption is 13 and 10, respectively, which is more than the tank capacity. In fact, all routes use up an amount of fuel more than 9 so our only chance is to refuel in airport 6. There are three possible routes to it: 1-2-6, 1-4-6 and 1-5-2-6. The first two are obviously the shorter ones (flights 1-2, 5-2, 2-6, 1-4 and 4-6 require an equal amount of time). After we fill up the tank in 6, if we go to 2 we still won’t be able to continue to 3 – we’ll be short fuel with one unit. The only route is through 4 and although we’ll have no fuel when we reach 3, we will be saved. To sum up, the optimal routes are 1-2-6-4-3 and 1-4-6-4-3. They are both represented by four 90-degree arcs, which makes their total length equal to Earth’s equator, or 2πR. Consequently, the time required to travel that distance is 2πR/V ≈ 12,566370614359172953850573533118.