Cyber APIO: Minimum Travel Time

In the year 3742, the stage is set for the APIO contest in Cyberland! There are \(N\) countries (numbered from 0 to \(N-1\)) and \(M\) bidirectional roads connecting them. You are starting at country 0 and must reach Cyberland located at country \(H\). Each road \(i\) connects two distinct countries \(x[i]\) and \(y[i]\) and takes \(c[i]\) time units to traverse.

Every country \(i\) has a special ability given by an array arr (with \(arr[0] = arr[H] = 1\)) that works as follows:

• If \(arr[i] = 0\), then when you pass through country \(i\) you can instantly reset your current accumulated travel time to 0.
• If \(arr[i] = 1\), no special action is available.
• If \(arr[i] = 2\), then when you pass through country \(i\) you have the option of halving your current accumulated travel time. However, you can use the halving ability at most \(K\) times overall.

Whenever you arrive at a country, you may choose to use its special ability (at most once per visit). Note that you are allowed to visit a country multiple times, and each visit gives you a fresh opportunity to use its ability (subject to the overall constraints for halving).

Your task is to determine the minimum time required to travel from country 0 to country \(H\). If there is no valid route, output \(-1\).

The function to implement is:

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr);

Your returned answer will be accepted if \( \frac{|ans_1 - ans_2|}{\max\{ans_2,1\}} \le 10^{-6} \).

inputFormat

The input consists of:

• An integer \(N\) representing the number of countries.
• An integer \(M\) representing the number of roads.
• An integer \(K\) representing the maximum number of times you can use the halving ability (i.e. for countries with \(arr[i]=2\)).
• An integer \(H\) representing the destination country's index.
• Three arrays of length \(M\): x, y, and c, where the \(i\)th road connects country \(x[i]\) and \(y[i]\) with a travel time of \(c[i]\).
• An array arr of length \(N\), where arr[i] indicates the special ability of country \(i\) (0 for reset, 1 for none, 2 for halving). It is guaranteed that arr[0] = arr[H] = 1.

Input is given in a single test case.

outputFormat

Output a single number, the minimum travel time from country 0 to country \(H\). If it is impossible to reach country \(H\), output \(-1\).

sample

3 2 1 2
0 1
1 2
5 5
1 2 1

7.5