← 返回题目列表

Codeforces · 2057/E2

E2. 另一个图练习(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。版本之间的区别在于,在这个版本中,对$$$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 \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$$$。

保证所有测试用例集的 $$$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$$$。