| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 71 | 17 | 16 | 27.119% |
The great Emperor, Lord Pooty, decided to retire and would like to hand over the crown to one of his many sons. In the spirit of democracy, he decided to do this with a vote! His kingdom consists of $N$ cities labelled from 0ドル$ to $N - 1$. Of these $N$ cities, $K$ of them are voting cities where voting can be done. The $i$th voting city is $T_i$.
As a reponsible member of society, you decided that it is only right for you to do your civic duty. You are to travel to one of the designated voting cities to vote! There are $E$ roads that can be used. Road $j$ connects city $U_j$ to city $V_j$ in one direction and has a toll of $C_j$. Luckily, due to this event, local cities have opened a ticket system to reduce the cost of traveling.
There are 5ドル$ different types of tickets to choose from, numbered from type 1ドル$ to type 5ドル$. A ticket of type $x$ will reduce the cost of the toll on a road by $(10x)\%$. In other words, the cost of the road will be multiplied by $\left(1 - \frac{x}{10}\right)$ if a ticket of type $x$ is used.
However, there are a few rules regarding the tickets. You cannot use more than one ticket on one road to stack the effects. You are only allowed to buy at most one of each ticket at the start of your journey. For example, you can choose to buy one type 1ドル$ ticket and one type 2ドル$ ticket but are not allowed to buy two type 2ドル$ tickets. This is to prevent people from hoarding the tickets. You are only allowed to buy the tickets at the start of your journey.
You are a busy man and unfortunately, you do not know which city you may start your journey from, nor do you know the ticket prices. You have made a list of $Q$ possible situations, comprised of a starting city $S$ and ticket prices $P_1,ドル $P_2,ドル $P_3,ドル $P_4$ and $P_5$ for the 5ドル$ tickets. It is possible that a certain ticket may not even be available, and in that case the ticket price will be $-1$.
For each of these situations, find the minimum cost to one of the voting city if it is reachable by road. Do note that not every city is reachable from every other and you may have to walk..
Your program must read from standard input.
The first line of input contains 3ドル$ integers $N,ドル $E$ and $K$ representing the number of cities, number of roads and number of voting cities respectively. The second line contains $K$ integers, the $i$th one representing $T_i,ドル the $i$th voting city.
The next $E$ contain 3ドル$ integers each. The $j$th of these lines consists of $U_j,ドル $V_j$ and $C_j$ respectively, representing a unidirectional road from $U_j$ to $V_j$ with cost $C_j$. It is guaranteed that $C_j$ is divisible by 10ドル$.
The next line contains a single integer $Q,ドル representing the number of situations to be considered.
The next $Q$ lines contain 6ドル$ integers $S,ドル $P_1,ドル $P_2,ドル $P_3,ドル $P_4$ and $P_5$ representing the starting city and the prices of the tickets of type 1ドル$ to type 5ドル$ respectively. Note that the starting city and ticket prices can differ across the different situations provided.
Your program must print to standard output.
Output $Q$ lines with 1ドル$ integer on each line, representing the lowest cost to a voting city for each situation in the order provided in the input. If a path does not exist for a situation, print $-1$ instead.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | There are no tickets sold. $P_i = -1$ for all $i$. $Q = 1$ and $K = 1$ |
| 2 | 5 | There are no tickets sold. $P_i = -1$ for all $i$. $K = 1$ |
| 3 | 5 | There are no tickets sold. $P_i = -1$ for all $i$. |
| 4 | 5 | $Q = 1$ and $K = 1$ |
| 5 | 5 | $K = 1$ |
| 6 | 10 | Each situation has at most 1ドル$ ticket available. |
| 7 | 15 | 1ドル ≤ N ≤ 100,ドル 1ドル ≤ E ≤ 1000$ |
| 8 | 50 | - |
3 2 1 2 0 1 100 1 2 200 1 0 10 20 1000 2000 -1
280
In the only situation given, the optimal solution would be to buy the type 2ドル$ ticket and use it on the 1ドル → 2$ road and the type 1ドル$ ticket and use it on the 0ドル → 1$ road. This would have a cost of 200ドル\left(1 - \frac{2}{10}\right) + 100\left(1 - \frac{1}{10} \right) + 10 +たす 20 =わ 160 +たす 90 +たす 10 +たす 20 =わ 280$.
This testcase is valid for subtasks 4,5, 7 and 8.
2 0 1 1 1 0 -1 -1 -1 -1 -1
-1
There is no road from your starting point to the only voting city. Thus, output $-1$.
This testcase is valid for all subtasks.
6 3 2 4 5 0 4 100 1 4 200 2 5 300 4 0 -1 -1 -1 -1 -1 1 20 40 10 100 4 2 1 2 3 4 0 3 0 -1 0 0 0
100 104 150 -1
This testcase is valid for subtasks 7 and 8.