U475857 Floyd 必刷题 #1

qqw $\dots$

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

无

无

对于 $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/) 戳这里。