分数: 450 点
问题陈述
有 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 每个桥至少使用一次。
只考虑过桥的时间。
您可以以任何顺序和任何方向穿过给定的桥梁。
约束
- 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
- 所有输入值均为整数。
- 可以使用一些桥梁在任意两个岛屿之间旅行。
输入
输入由标准输入按以下格式给出:
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-第一个查询作为整数。
示例输入 1
3 5 1 2 10 1 3 20 1 3 30 2 3 15 2 3 25 2 1 1 2 3 5
示例输出 1
25 70
对于第一个查询,我们需要找到从岛屿出发的最短时间 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 在第二行。
示例输入 2
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
示例输出 2
5 3
对于每个查询,您可以在任一方向穿过指定的桥梁。
示例输入 3
5 5 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 1 5 1000000000 1 1 3
示例输出 3
4000000000
请注意,答案可能不适合 32位整数。