如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。
现给定一棵仙人掌,每条边有一个正整数权值,每次给 $k$ 个点(可以存在相同点),问从它们中选出两个点(可以相同),它们之间最短路的最大值是多少。
输入格式
第一行两个非负整数 $n, m$,表示仙人掌的点数和边数。
接下来 $m$ 行,每行三个正整数 $v, u, w$ $(1 \le v, u \le n)$,表示 $v$ 与 $u$ 之间有一条边权为 $w$ 的无向边。点从 $1$ 开始编号。
保证输入的图是一棵仙人掌,保证没有自环,但可能有重边。
接下来一行一个非负整数 $Q$,表示询问个数。
接下来 $Q$ 行每行第一个数是正整数 $\mathrm{cnt}$ 表示点数,接下来 $\mathrm{cnt}$ 个数表示给定的点。
输出格式
对每个询问输出一个数,表示该询问对应的最大值。
样例一
input
10 14 10 7 1 3 8 7 1 6 9 7 2 10 8 9 9 1 7 1 8 5 2 4 5 4 1 7 4 2 9 8 9 3 3 8 4 2 1 6 5 7 9 10 6 2 9 5 2 8 10 3 8 7 6 2 6 4 3 3 4 2 1 10
output
11 20 25 27 19 0
explanation
前五个询问的答案路径分别为(如果有重边则显然走较短的边):
$9 \rightarrow 8 \rightarrow 5$
$8 \rightarrow 9 \rightarrow 7 \rightarrow 10$
$8 \rightarrow 9 \rightarrow 7 \rightarrow 1 \rightarrow 6$
$4 \rightarrow 8 \rightarrow 9 \rightarrow 7 \rightarrow 1 \rightarrow 6$
$2 \rightarrow 9 \rightarrow 8 \rightarrow 4$
最后一个询问的答案显然是$0$。
限制与约定
边权不超过 $2 ^ {31} - 1$。
$\mathrm{tot}$ 表示询问的总点数。
对于 5% 的数据,$n, \mathrm{tot} \le 7$。
对于 10% 的数据,$n, \mathrm{tot} \le 5000$。
对于另外 10% 的数据,$Q \le 10$,其中存在 $Q \le 2$ 的数据。
对于另外 30% 的数据,$m = n - 1$。
对于 100% 的数据,$n, \mathrm{tot} \le 300000$。
此外为了照顾被卡常数的同学,本题存在过渡数据。
时间限制:$5\texttt{s}$
空间限制:$512\texttt{MB}$
来源
matthew99
题解
https://matthew99.blog.uoj.ac/blog/241