这是问题的简单版本。版本之间的区别在于,在这个版本中,对$$$m$$$有一个额外的约束。只有解决了该问题的所有版本,您才能破解。
最近,“T一代”的导师们需要举办一场训练赛。他们漏掉了一个问题,而且比赛中图表上没有任何问题,所以他们提出了以下问题。
给您一个带 $$$n$$$ 个顶点和 $$$m$$$ 个边的连通加权无向图,该图不包含自环或多重边。
有 $$$q$$$ 形式的查询 $$$(a, b, k)$$$:在从顶点 $$$a$$$ 到顶点 $$$b$$$ 的所有路径中,找到该路径上最小的第 $$$k$$$ 边的最大权重$$$^{\dagger}$$$。
导师们认为这个问题听起来很有趣,但有一个问题。他们不知道如何解决。帮助他们解决问题,因为距离比赛开始只剩下几个小时了。
$$$^{\dagger}$$$ 设 $$$w_1 \ge w_2 \ge \ldots \ge w_{h}$$$ 为路径中所有边的权重,按非递增顺序。该路径上第 $$$k$$$ 边的最大权重为 $$$w_{k}$$$。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。
每组测试用例的第一行包含三个整数 $$$n、m$$$ 和 $$$q$$$ ($$$2 \le n \le 400$$$, $$$n - 1 \le m \le \operatorname{min}(\mathbf{400}, \frac{n \cdot (n - 1)}{2})$$$, $$$1 \le q \le 3 \cdot 10^5$$$) — 分别是顶点数、边数和问题数。
每组测试用例的以下 $$$m$$$ 行均包含三个整数 $$$v、u$$$ 和 $$$w$$$ ($$$1 \le v, u \le n$$$, $$$1 \le w \le 10^9$$$) - 分别是图的下一条边的末端及其权重。保证图不包含自环和重边。
每组测试用例的以下 $$$q$$$ 行均包含三个整数 $$$a、b$$$ 和 $$$k$$$ ($$$1 \le a, b \le n$$$, $$$k \ge 1$$$) - 下一个问题。保证从顶点$$$a$$$到顶点$$$b$$$的任何路径至少包含$$$k$$$边。
保证所有测试用例集的 $$$n$$$ 值的总和不超过 $$$400$$$。
保证所有测试用例集的 $$$m$$$ 值的总和不超过 $$$400$$$。
保证所有测试用例集的 $$$q$$$ 值的总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,输出所有问题的答案。
示例
输入 #1
3 4 4 2 1 2 2 2 4 2 1 3 4 3 4 1 1 4 2 2 3 1 6 7 3 1 2 10 2 3 3 3 4 9 4 5 2 5 6 1 2 4 10 4 6 10 1 6 3 1 6 2 2 4 1 11 17 10 1 4 5 1 3 19 1 2 10 3 2 13 4 5 1 4 6 11 3 5 9 3 6 18 2 7 17 5 8 15 5 10 8 6 9 4 7 10 20 7 8 16 8 11 3 9 11 6 10 11 14 3 11 1 3 11 3 1 11 1 1 11 4 1 11 3 8 2 2 10 4 1 3 9 2 3 9 1 6 7 3
输出 #1
1 2 2 9 9 11 3 11 1 3 10 8 4 11 4
注意
在第一组测试用例中,第一个查询中的最佳路径之一是路径 $$$1 \rightarrow 3 \rightarrow 4$$$;该路径上的第$$$2$$$边的最大权重为$$$1$$$。在第二个查询中,最佳路径之一是 $$$2 \rightarrow 4 \rightarrow 3$$$; $$$1$$$-st 边的最大权重为$$$2$$$。
在第二组输入数据中,第一个查询中的最优路径之一是路径 $$$1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6$$$;该路径上边的 $$$3$$$-rd 最大权重为 $$$2$$$。