U475857 Floyd 必刷题 #1

qqw $\dots$

给定一个 $n$ 个节点 $m$ 条边的无向图。 共 $q$ 次询问，每次给定 $k$ 个必须经过的边的编号，问从 $1 \sim n$ 的最短路径是多少。 **只要经过了这些给定的边即可，不在意经过顺序。** **可能重边，但是不可能自环。**

第一行，两个正整数 $n,m$。 接下来 $m$ 行，第 $i$ 行 $3$ 个整数表示编号为 $i$ 的无向边 $(u_i, v_i, w_i)$，边权为 $w_i (1 \le w_i \le 10^5)$。 接下来一行输入一个正整数 $q$。 接下来 $q$ 次询问，每次询问： - 第一行给定一个整数 $k$，表示必须要经过的边的个数。 - 第二行共 $k$ 个数 $a_1,a_2,\cdots,a_k$，表示必须经过编号为 $a_i$ 的边（保证 $a$ 中没有重复的数）。

共 $q$ 行，第 $i$ 行表示第 $i$ 次询问的答案。

对于 $20\%$ 的数据：$1 \le n \le 10,1 \le m \le 50,1 \le q \le 3000,1 \le k \le 5$。 对于另外 $80\%$ 的数据：$1 \le n \le 500,1 \le m \le 2\times 10^5,1 \le q \le 3000,1 \le k \le 5$。 本题仅有一个 Subtasks，你必须答对所有测试点才能得分（出题人非常善良 qqw）。 注：[题解 & 算法介绍](https://george110915.github.io/Floyd%20%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0%E6%97%A5%E8%AE%B0/) 戳这里。