题目描述

译自 NOISG 2022 Final T1. Voting Cities

伟大的皇帝普蒂勋爵决定退休，并希望将王位传给他的众多儿子之一。为了体现民主精神，他决定通过投票来决定！他的王国包含 $N$ 个城市，编号从 $0$ 到 $N-1$。其中 $K$ 个城市是投票城市，可以进行投票。第 $i$ 个投票城市为 $T_i$。

作为社会中负责任的一员，你认为履行公民义务是正确的。你需要前往一个指定的投票城市进行投票！有 $E$ 条道路可供使用。第 $j$ 条道路从城市 $U_j$ 单向连接到城市 $V_j$，通行费为 $C_j$。幸运的是，由于这次活动，当地城市开放了票务系统以降低旅行成本。

有 $5$ 种不同类型的票可供选择，编号从 $1$ 到 $5$。类型 $x$ 的票将使道路通行费降低 $(10x)\%$。换句话说，若使用类型 $x$ 的票，道路费用将乘以 $(1 - \frac{x}{10})$。

然而，票务系统有一些规则。你不能在一条道路上使用多张票叠加效果。你只能在旅程开始时最多购买每种类型各一张票。例如，你可以选择购买一张类型 $1$ 的票和一张类型 $2$ 的票，但不能购买两张类型 $2$ 的票。这是为了防止囤积票务。你只能在旅程开始时购买票。

你是一个忙碌的人，不确定从哪个城市开始旅程，也不知道票价。你列出了 $Q$ 种可能情况，每种情况包括一个起始城市 $S$ 和 $5$ 种票的票价 $P_1, P_2, P_3, P_4, P_5$。某些票可能不可用，在这种情况下票价为 $-1$。

对于每种情况，找出通过道路到达一个投票城市的最低成本。注意，并非每个城市都能到达其他所有城市，你可能需要步行……

输入格式

程序需从标准输入读取数据。

输入的第一行包含三个整数 $N, E, K$，分别表示城市数量、道路数量和投票城市数量。

第二行包含 $K$ 个整数，第 $i$ 个表示 $T_i$，即第 $i$ 个投票城市。

接下来的 $E$ 行，每行包含三个整数。第 $j$ 行包含 $U_j, V_j, C_j$，表示从 $U_j$ 到 $V_j$ 的单向道路，费用为 $C_j$。保证 $C_j$ 可被 $10$ 整除。

下一行包含一个整数 $Q$，表示需要考虑的情况数量。

接下来的 $Q$ 行，每行包含 $6$ 个整数 $S, P_1, P_2, P_3, P_4, P_5$，分别表示起始城市和类型 1 到类型 5 的票价。注意，不同情况的起始城市和票价可能不同。

输出格式

程序需向标准输出输出结果。

输出 $Q$ 行，每行一个整数，按输入顺序表示每种情况下到达投票城市的最低成本。若某种情况下无法到达投票城市，则输出 $-1$。

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

280

在给定的唯一情况下，最优解是购买类型 $2$ 的票并在 $1 \rightarrow 2$ 道路上使用，购买类型 $1$ 的票并在 $0 \rightarrow 1$ 道路上使用。成本为 $200 \times (1 - \frac{2}{10}) + 100 \times (1 - \frac{1}{10}) + 10 + 20 = 160 + 90 + 10 + 20 = 280$。

这个样例满足子任务 $4, 5, 7, 8$ 的限制。

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

-1

从起始城市到唯一的投票城市没有道路。因此，输出 $-1$。

这个样例满足所有子任务的限制。

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

这个样例满足子任务 $7, 8$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 5000$
• $0 \leq E \leq 10000$
• $1 \leq Q \leq 100$
• $0 \leq K \leq N$
• $0 \leq T_i < N$，对于所有 $1 \leq i \leq K$
• $T_i \neq T_j$，对于所有 $1 \leq i < j \leq K$
• $1 \leq C_i \leq 10^9$，对于所有 $1 \leq i \leq E$
• $C_i$ 为 $10$ 的倍数，对于所有 $1 \leq i \leq E$
• $0 \leq U_i, V_i < N$ 且 $U_i \neq V_i$，对于所有 $1 \leq i \leq E$
• $-1 \leq P_i \leq 10^9$，对于所有 $1 \leq i \leq 5$

详细子任务附加限制及分值如下表所示：