← 返回题目
题库练习 观光旅游
← 上一题 下一题 →

A5164 | 观光旅游

时间限制2s
内存限制512MB
通过 / 提交0/0

题目描述

有 $N$ 座岛屿和 $M$ 条双向桥梁，每条桥梁连接两个岛屿。岛屿和桥梁分别编号为 $1,2,\cdots,N$ 和 $1,2,\cdots,M$。
桥梁 $i$ 连接岛屿 $U_i$ 和 $V_i$ ，在任一方向上穿过它所需的时间是 $T_i$ 。
没有桥梁会连接同一个岛屿，但两个岛屿可以通过多座桥梁直接连接。
人们可以使用一些桥梁在任意两个岛屿之间旅行。

您会收到 $Q$ 的查询，请逐一回答。第 $i$ 个查询如下：

>你会得到 $K_i$ 不同的桥：桥 $B_{i,1},B_{i,2},\cdots,B_{i,K_i}$。
>找到使用这些桥梁从 $1$ 岛屿到 $N$ 岛屿至少一次所需的最短时间。
>只考虑过桥所花费的时间。
>你可以以任何顺序和任何方向穿过给定的桥梁。

输入格式

第一行输入两个正整数 $N,M$ $(2 \leq N \leq 400;N-1 \leq M \leq 2 \times 10^5)$ ，表示岛屿个数。

接下来 $M$ 行，每行输入三个整数 $U,V,T$ $(1 \leq U_i \lt V_i \leq N;1 \leq T_i \leq 10^9)$ ，表示这条桥梁连接的两个岛屿以及通过这条桥梁需要花费的时间。

第 $M+1$ 行输入一个正整数 $Q$ $(1 \leq Q \leq 3000)$ ，表示询问次数。

接下来 $Q$ 个询问，每个询问输入两行：

第一行输入一个正整数 $K$ $(1 \leq K_i \leq 5)$，表示这次询问需要通过的桥梁个数。

第二行输入 $K$ 个正整数 $B_1,B_2,\cdots,B_k$ $(1 \leq B_1 \lt B_2 \lt \cdots \lt B_K \leq M)$，表示这次询问需要通过的桥梁的编号。

输出格式

输出 $Q$ 行，每行一个整数。

第 $i$ 个整数表示第 $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
输入 #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
C++ 编辑器
输入
输出