Sightseeing Tour

题目描述

有 $N$ 个岛屿和 $M$ 座连接两个岛屿的双向桥。岛屿和桥分别编号为 $1,2,\ldots,N$ 和 $1,2,\ldots,M$。
桥 $i$ 连接岛屿 $U_i$ 和 $V_i$，并且无论哪个方向通过它都需要时间 $T_i$。
没有桥将某个岛屿连接到它自身，但两个岛屿之间可能有多于一座的直接桥。
任意两个岛屿之间都可以通过若干座桥到达。 给出 $Q$ 个查询，请回答每个查询。第 $i$ 个查询如下：

给定 $K_i$ 座互不相同的桥：桥 $B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}$。
求从岛屿 $1$ 到岛屿 $N$ 的最短所需时间，要求在行程中至少各使用这些桥一次。
只计算过桥所花费的时间。
你可以以任意顺序、任意方向通过这些指定的桥。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $U_1$ $V_1$ $T_1$ $U_2$ $V_2$ $T_2$ $\vdots$ $U_M$ $V_M$ $T_M$ $Q$ $K_1$ $B_{1,1}$ $B_{1,2}$ $\cdots$ $B_{1,{K_1}}$ $K_2$ $B_{2,1}$ $B_{2,2}$ $\cdots$ $B_{2,{K_2}}$ $\vdots$ $K_Q$ $B_{Q,1}$ $B_{Q,2}$ $\cdots$ $B_{Q,{K_Q}}$

输出格式

输出 $Q$ 行。第 $i$ 行（$1 \leq i \leq Q$）应包含第 $i$ 个查询的答案，作为一个整数。

3 5
1 2 10
1 3 20
1 3 30
2 3 15
2 3 25
2
1
1
2
3 5

25
70

6 6
1 5 1
2 5 1
2 4 1
3 4 1
3 6 1
1 6 1
2
5
1 2 3 4 5
1
5

5
3

5 5
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
1 5 1000000000
1
1
3

4000000000

提示

$2 \leq N \leq 400$ $N-1 \leq M \leq 2 \times 10^5$ 1 \leq U_i < V_i \leq N $1 \leq T_i \leq 10^9$ $1 \leq Q \leq 3000$ $1 \leq K_i \leq 5$ $1 \leq B_{i,1} < B_{i,2} < \cdots < B_{i,K_i} \leq M$ 所有输入值均为整数。 任意两个岛屿之间都可以通过若干座桥到达。对于第一个查询，我们需要找到从岛屿 $1$ 到岛屿 $3$ 且必须使用桥 $1$ 的最短时间。 最短时间是先使用桥 $1$ 从岛屿 $1$ 到岛屿 $2$，然后使用桥 $4$ 从岛屿 $2$ 到岛屿 $3$。所需时间为 $10 + 15 = 25$。 因此，在第一行输出 $25$。 对于第二个查询，我们需要找到从岛屿 $1$ 到岛屿 $3$ 且必须同时使用桥 $3$ 和桥 $5$ 的最短时间。 最短时间是先使用桥 $3$ 从岛屿 $1$ 到岛屿 $3$，然后使用桥 $5$ 到岛屿 $2$，最后使用桥 $4$ 返回到岛屿 $3$。所需时间为 $30 + 25 + 15 = 70$。 因此，在第二行输出 $70$。
对于每个查询，你可以以任意方向通过指定的桥。
注意答案可能无法用 32 位整数表示。

标签: AtCoder|abc369E

来源

AtCoder|abc369E