Background

Due to some BUGs, submitting with C++14 (GCC9) will cause a compilation error. Please use C++14 and other languages to submit.

When submitting, you do not need to include cyberland.h. In your submitted code, 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)

Problem Description

The year 3742 has arrived, and now it is Cyberland’s turn to host APIO. In this world, there are $N$ countries, numbered from $0$ to $N - 1$, and there are $M$ bidirectional roads (each edge can be traveled in both directions), numbered from $0$ to $M - 1$. Each road connects two different countries, $x[i]$ and $y[i]$, and it takes time $c[i]$ to travel along that road. All contestants, except the one from your country, have already gathered in Cyberland to attend APIO. You live in country $0$, and Cyberland is country $H$. As the smartest person in your country, your help is urgently needed. More specifically, you need to determine the minimum time required to reach Cyberland from your country.

When passing through some countries, you can reset your current total travel time. Also, some other countries can divide your current total travel time by $2$ when you pass through them (we call this the “divide-by-2 ability”). You may pass through a country multiple times. Each time you pass through a country, you may choose whether to use that country’s special ability. However, each time you pass through a country, you can use its special ability at most once (if you pass through a country multiple times, you may use its special ability at most once each time). In addition, to avoid being caught by the Cyberland Chemical Foundation, you may use the “divide-by-2 ability” at most $K$ times. Once you arrive in Cyberland, you cannot move anywhere else, because the great APIO contest is about to begin.

You are given an array $arr$, where $arr[i]$ represents the special ability of country $i \ (0 \le i \le N - 1)$. Each country has one of the following $3$ special abilities:

• $arr[i] = 0$ means this country can set the current total travel time to $0$.
• $arr[i] = 1$ means this country does not change your current total travel time.
• $arr[i] = 2$ means this country has the ability to divide the current total travel time by $2$.

It is guaranteed that $arr[0] = arr[H] = 1$. In other words, neither Cyberland nor your home country has any special ability.

Your country does not want to miss any moment of APIO, so you need to find the shortest time to reach Cyberland. If you cannot reach Cyberland, your answer should be $-1$.

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);

• $N$: the number of countries.
• $M$: the number of bidirectional roads.
• $K$: the maximum number of times the “divide-by-2 ability” can be used.
• $H$: the index of the country “Cyberland”.
• $x, y, c$: three arrays of length $M$. The triplet $(x[i], y[i], c[i])$ indicates that the $i$-th bidirectional edge connects countries $x[i]$ and $y[i]$, and the time cost to travel through it is $c[i]$.
• $arr$: an array of length $N$. $arr[i]$ indicates the special ability of country $i$.
• If you can reach Cyberland, the function should return the shortest time needed to travel from your country to Cyberland; otherwise, return $-1$.
• This process may be called multiple times.

Suppose the contestant’s answer is $ans_1$, and the standard output is $ans_2$. Your output is considered correct if and only if $\dfrac{|ans_1-ans_2|}{\max\{ans_2,1\}} \le 10 ^ {-6}$.

Note: Since the function may be called multiple times, contestants need to be careful about the impact of leftover data from previous calls on subsequent calls.

Input Format

The sample grader reads input in the following format:

• Line $1$: $T$

For each of the $T$ test cases:

• Line $1$: $N \ M \ K$
• Line $2$: $H$
• Line $3$: $arr[0] \ arr[1] \ arr[2] \ \cdots \ arr[N - 1]$
• Line $4 + i \ (0 \le i \le M - 1)$: $x[i] \ y[i] \ c[i]$

Output Format

The sample grader prints your answer in the following format:

For each test case:

• Line $1$: the return value of solve.

3 2 30
2
1 2 1
1 2 12
2 0 4

4

4 4 30
3
1 0 2 1
0 1 5
0 2 4
1 3 2
2 3 4

2

Hint

Examples

Sample 1

Consider the following call:

solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});

The only path to reach Cyberland is $0 \rightarrow 2$, because after you arrive in Cyberland you cannot move to any other place. The travel time is computed as follows:

Sample 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});

There are two paths from your country to Cyberland: $0 \rightarrow 1 \rightarrow 3$ and $0 \rightarrow 2 \rightarrow 3$.

If you choose the path $0 \rightarrow 1 \rightarrow 3$, the travel time is computed as follows:

If you choose the path $0 \rightarrow 2 \rightarrow 3$, the travel time is computed as follows:

Therefore, the above call should return $2$.

Constraints

• $2 \le N \le 10^5 , \sum N \le 10^5$.
• $0 \le M \le \min\{10^5, \dfrac{N(N-1)}{2} \}, \sum M \le 10^5$.
• $1 \le K \le 10^6$.
• $1 \le H < N$.
• $0 \le x[i], y[i] < N , x[i] \neq y[i]$.
• $1 \le c[i] \le 10^9$.
• $arr[i] \in \{0, 1, 2\}$.
• It is guaranteed that there is at most one road connecting any pair of countries.

Subtasks

1. (5 points): $N \le 3, K \le 30$.
2. (8 points): $M = N - 1, K \le 30, arr[i] = 1$. You can travel from any country to any other country using these $M$ roads.
3. (13 points): $M = N - 1, K \le 30, arr[i] \in \{0, 1\}$. You can travel from any country to any other country using these $M$ roads.
4. (19 points): $M = N - 1, K \le 30, x[i] = i, y[i] = i + 1$.
5. (7 points): $K \le 30, arr[i] = 1$.
6. (16 points): $K \le 30, arr[i] \in \{0, 1\}$.
7. (29 points): $K \le 30$.
8. (3 points): No special constraints.

Translated by ChatGPT 5