题目描述
给定一个包含 n 个顶点和 m 条边的连通带权无向简单图。边权均为正整数。对一条从某个顶点到另一个顶点的简单路径,把路径上的边权按从大到小排列为 w1≥w2≥⋯,称 wk 为这条路径的第 k 大边权。
小 W 需要回答 q 次询问。每次询问给出 (a,b,k),请在所有从 a 到 b 的简单路径中,找出路径第 k 大边权的最小可能值。数据保证每条从 a 到 b 的路径至少包含 k 条边,因此第 k 大值始终有定义。
输入格式
第一行一个整数 t,表示测试组数。
每组数据先给出 n,m,q,满足 2≤n≤400、n−1≤m≤400、1≤q≤3×105。随后给出 m 条边 u,v,w(1≤w≤109)和 q 个询问 (a,b,k)。保证图连通、无自环、无重边;所有测试组的 n,m,q 总和分别不超过 400,400,3×105。
输出格式
按询问顺序输出答案。每组数据的所有答案占一行,数值之间用空格分隔。
样例 1 输入
1
4 4 2
1 2 2
2 4 2
1 3 4
3 4 1
1 4 2
2 3 1
样例 1 输出
1 2
样例 1 解释
第一问要求从 1 到 4 的路径上第二大的边权尽量小。路径 1→3→4 的边权为 4,1,第二大为 1,因此答案至多为 1;由于任意两条边的路径至少有一条边权不小于 1,答案就是 1。第二问从 2 到 3 且 k=1,路径 2→4→3 的最大边权为 2,所以答案为 2。
数据范围
2≤n≤400,n−1≤m≤400,1≤q≤3×105,1≤w≤109;所有测试组的 n,m,q 总和分别不超过 400,400,3×105。
| 数据类别 |
分值 |
测试点 |
附加条件 |
| A |
20 |
1∼4 |
n≤8,q≤30 |
| B |
5∼8 |
图为树 |
| C |
15 |
9∼12 |
k=1 |
| D |
13∼15 |
m≤80 |
| E |
30 |
16∼20 |
无附加限制 |