시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB63350.000%

문제

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 ≤ N ≤ 5000$
  • $ 0 ≤ E ≤ 10000$
  • $1 ≤ Q ≤ 100$
  • $0 ≤ K ≤ N$
  • $0 ≤ T_i < N$ for all $1 ≤ i ≤ K$
  • $T_i \ne T_j$ for all $1 ≤ i < j ≤ K$
  • $1 ≤ C_i ≤ 10^9$ for all $1 ≤ i ≤ E$
  • $C_i$ is a multiple of $10$ for all $1 ≤ i ≤ E$
  • $0 ≤ U_i , V_i < N$ and $U_i \ne V_i$ for all $1 ≤ i ≤ E$
  • $-1 ≤ P_i ≤ 10^9$ for all $1 ≤ i ≤ 5$

서브태스크

번호배점제한
15

There are no tickets sold. $P_i = -1$ for all $i$. $Q = 1$ and $K = 1$

25

There are no tickets sold. $P_i = -1$ for all $i$. $K = 1$

35

There are no tickets sold. $P_i = -1$ for all $i$.

45

$Q = 1$ and $K = 1$

55

$K = 1$

610

Each situation has at most $1$ ticket available.

715

$1 ≤ N ≤ 100$, $1 ≤ E ≤ 1000$

850

-

예제 입력 1

3 2 1
2
0 1 100
1 2 200
1
0 10 20 1000 2000 -1

예제 출력 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

2 0 1
1
1
0 -1 -1 -1 -1 -1

예제 출력 2

-1

There is no road from your starting point to the only voting city. Thus, output $-1$.

This testcase is valid for all subtasks.

예제 입력 3

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

예제 출력 3

100
104
150
-1

This testcase is valid for subtasks 7 and 8.

채점 및 기타 정보

  • 예제는 채점하지 않는다.