Environment-Friendly Travel#9702
Taking holidays unfortunately has a carbon footprint. The CO2-cost of a kilometre travelled depends on the mode of transportation. For instance, train travel is less costly than bus travel, which is itself less costly than car travel.
Your objective is to plan a holiday trip from your house, given by 2D coordinates (x_s, y_s), to your travel destination, given by (x_d, y_d). Being aware of the environmental impact of travel, you want to minimize the CO2-cost of your holiday, but you still want to keep the total number of kilometres travelled within a given budget .
To aid you in planning, you have access to a map of stations, possibly linked by different modes of transportation (airplane, train, etc.) numbered , ..., . Each mode has a CO2-cost per distance unit c_1, ..., c_t. You can travel by car from your home to the destination, from your home to any station, and from any station to the destination point, at a cost c_0 per distance unit. c_0 is always greater than any of c_1, ..., c_t.
Each of the stations has coordinates (x_i, y_i) for = , ..., - . Each station may be connected to some other stations via one or several of the modes. Each connection works both ways, so only one direction has to be listed. There can be multiple modes of transportation available between two stations. You can only travel between two stations via their connections using the available transportation modes (car travel is not allowed between stations).
The distance between two points and is the 2D distance between (x_a, y_a) and (x_b, y_b), rounded to the nearest integer above:
and the CO2-cost of travel between and , using transport mode is:
(, , ) = c_i * (, )
Given two source–destination coordinates, a budget expressed in distance units, a list of transportation modes and their respective CO2-costs, and the station network, your task is to compute the minimal CO2-cost possible while traveling at most kilometres.
Consists of the following lines:
Line 1 contains two space-separated integers x_s and y_s, the coordinates of your house.
Line 2 contains two space-separated integers x_d and y_d, the coordinates of your destination.
Line 3 contains an integer ( ≤ ≤ ), the maximal distance (in kilometres) that you accept to travel.
Line 4 contains an integer c_0, the CO2-cost per distance unit of traveling by car.
Line 5 contains an integer ( ≤ ≤ ), the number of modes of transportation (beside cars).
Line + , for ≤ ≤ , contains the integer c_i, the CO2-cost per distance unit of transportation mode ( ≤ c_1, ..., c_t < c_0 ≤ ).
Line + contains the integer ( ≤ ≤ ), the number of stations.
Line + + describes station ( ≤ < ) and contains + * l_i space-separated integers. The first three integers are x_i, y_i and l_i. The pair (x_i, y_i) represents the coordinates of station , while l_i is the number of links between station and other stations. The l_i remaining pairs of integers (, m_j) each describe a link to station ( ≤ < ) using transportation mode m_j ( ≤ m_j ≤ ). All links are bidirectional.
All inputs are integers. All coordinates are in [, ] * [, ]. For each station, there are at most links to other stations.
Print one integer representing the minimal feasible CO2-cost or if no feasible cost is found within the kilometre budget.
Example 1
The results corresponds to the CO2-cost of the following route:
from home at (, ) to station at (, ) by car for a cost of * sqrt(1^2 + 2^2) = ,
to station at (, ) via transportation mode for a cost of * sqrt(7^2 + 0^2) = ,
to the destination at (, ) by car for a cost of * sqrt(1^2 + 1^2) = for a total of .
This route is valid because the total distance travelled is + + = , within the allowed budget of .