The year 3742 has arrived, and now it is Cyberland's turn to host the APIO.
In this world, there are
Some countries can reset the amount of time you've spent traveling.
Also, some countries can divide your total travel time by
An array
, means this country sets the travel time to . , means the travel time remains unchanged at this country. , means this country divides the travel time by .
It is guaranteed that
Your country does not want to miss any moment of APIO, so you need to find the minimum amount of time to
reach Cyberland. If you cannot reach Cyberland, your answer should be
Implementation Details
You need to implement the following function:
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr);
: The number of countries. : The number of bidirectional roads. : The limit on divide-by-2 ability usage. : The index of the country Cyberland. : three arrays of length . the tuple represents the -th undirected edge which connects countries and with time cost . : an array of length . represents the special ability of country .- This procedure should return the minimum amount of time to reach Cyberland from your country if you
can reach Cyberland, and
if you cannot do so. - This procedure can be called more than once.
Assume that the return value of the contestant is
Note: Since the procedure can be called more than once, contestants need to pay attention to the impact of the remaining data of the previous call on the current call.
Example 1
Consider the following call:
solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});
The only path to Cyberland is
country number | travel time |
---|---|
Therefore, the procedure should return
Example 2
Consider the following call:
solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});
Two paths from your country to Cyberland are
If your path is
country number | travel time |
---|---|
If your path is
country number | travel time |
---|---|
Therefore, the procedure should return
Constraints
, and . , and . . . , and . . .- It is guaranteed that every pair of countries is connected by at most one road.
Subtasks
- (5 points):
. - (8 points):
, you can travel from any country to any other country via the edges. - (13 points):
, you can travel from any country to any other country via the edges. - (19 points):
. - (7 points):
. - (16 points):
. - (29 points):
. - (3 points): No additional constraints.
Sample Grader
The sample grader reads input in the following format:
- line
:
For each of the following
- line
: - line
: - line
: - line
:
The sample grader prints your answers in the following format:
For each test case:
- line
: the return value ofsolve
Attachment Package
The sample grader along with sample test cases are available here: cyberland.zip.
Comments