#CW36. 图上排名(graphquest)

图上排名(graphquest)

题目描述

给定一个包含 nn 个顶点和 mm 条边的连通带权无向简单图。边权均为正整数。对一条从某个顶点到另一个顶点的简单路径,把路径上的边权按从大到小排列为 w1≥w2≥⋯w_1 \ge w_2 \ge \cdots,称 wkw_k 为这条路径的第 kk 大边权。

小 W 需要回答 qq 次询问。每次询问给出 (a,b,k)(a,b,k),请在所有从 aa 到 bb 的简单路径中,找出路径第 kk 大边权的最小可能值。数据保证每条从 aa 到 bb 的路径至少包含 kk 条边,因此第 kk 大值始终有定义。

输入格式

第一行一个整数 tt,表示测试组数。

每组数据先给出 n,m,qn,m,q,满足 2≤n≤4002 \le n \le 400、n−1≤m≤400n-1 \le m \le 400、1≤q≤3×1051 \le q \le 3 \times 10^5。随后给出 mm 条边 u,v,wu,v,w(1≤w≤1091 \le w \le 10^9)和 qq 个询问 (a,b,k)(a,b,k)。保证图连通、无自环、无重边;所有测试组的 n,m,qn,m,q 总和分别不超过 400,400,3×105400,400,3\times 10^5。

输出格式

按询问顺序输出答案。每组数据的所有答案占一行,数值之间用空格分隔。

样例 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 解释

第一问要求从 11 到 44 的路径上第二大的边权尽量小。路径 1→3→41 \to 3 \to 4 的边权为 4,14,1,第二大为 11,因此答案至多为 11;由于任意两条边的路径至少有一条边权不小于 11,答案就是 11。第二问从 22 到 33 且 k=1k=1,路径 2→4→32 \to 4 \to 3 的最大边权为 22,所以答案为 22。

数据范围

2≤n≤4002 \le n \le 400,n−1≤m≤400n-1 \le m \le 400,1≤q≤3×1051 \le q \le 3\times 10^5,1≤w≤1091 \le w \le 10^9;所有测试组的 n,m,qn,m,q 总和分别不超过 400,400,3×105400,400,3\times 10^5。

数据类别 分值 测试点 附加条件
A 20 1∼41\sim 4 n≤8n \le 8,q≤30q \le 30
B 5∼85\sim 8 图为树
C 15 9∼129\sim 12 k=1k=1
D 13∼1513\sim 15 m≤80m \le 80
E 30 16∼2016\sim 20 无附加限制