AT_abc369_e [ABC369E] Sightseeing Tour

题目描述

题目大意

给你一张 $N$ 个点，$M$ 条边的无向图（可能有重边）。第 $i$ 条边的端点是 $U_i$ 和 $V_i$，长度是 $T_i$。

给定 $Q$ 个询问，每个询问会给出 $K$ 条边。对于每个询问，请求出经过这 $K$ 条边（一定经过这 $K$ 条边，但是也可以经过其他的边）的 $1$ 到 $N$ 的最短路的长度。

输入格式

第一行是两个正整数 $N,M$。

接下来 $M$ 行，第 $i+1$ 行输入编号为 $i$ 的边：$U_i,V_i,T_i$。

接下来一行，输入询问的个数 $Q$。

接下来 $Q \times 2$ 行，每两行描述一个询问。 每个询问的第一行是给出的边的数量 $K_i$，第二行有 $K_i$ 个数：$B_{i,1}\space B_{i,2}\cdots B_{i,K_i}$，表示给出的边的编号。

输出格式

对于每个询问，输出一行一个整数表示你的答案。

输入输出样例 #1

输入 #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

输入 #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

输入 #3

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

输出 #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$
• 所有输入值都是整数。
• 这个图是连通图。

translate by @wujiawei36