题目描述
极夜降临,冰洋上的 n 座港口被浮冰封锁,编号依次为 1,2,…,n。
勘测队标出了 m 条候选航道。第 i 条航道双向连接港口 ui 与 vi(ui=vi),其安全吨位为 wi。一艘船通过该航道时,排水量不能超过 wi。
一支船队可以选择任意一条从港口 s 到港口 t 的路线航行(s=t)。一条路线由一条或多条首尾相接的候选航道组成,同一座港口或同一条航道都可以重复经过。
设路线 P 经过的航道编号依次为 e1,e2,…,ek,则它的通行吨位定义为
cap(P)=1≤j≤kminwej.
对于每次询问 (s,t),请在所有从 s 到 t 的路线中最大化通行吨位,即求
P:s⇝tmaxcap(P).
如果不存在从 s 到 t 的路线,则输出 −1。
输入格式
第一行输入三个整数 n,m,q(2≤n≤2×105,0≤m≤2×105,1≤q≤2×105),分别表示港口数、候选航道数和询问数。
接下来 m 行,第 i 行输入三个整数 ui,vi,wi(1≤ui,vi≤n,ui=vi,1≤wi≤109),表示一条连接 ui 与 vi、安全吨位为 wi 的候选航道。两座港口之间可能有多条航道。
接下来 q 行,每行输入两个整数 s,t(1≤s,t≤n,s=t),表示一次询问。
输出格式
输出 q 行。第 i 行输出一个整数:
- 如果第 i 次询问中的两个港口连通,输出它们之间的最大通行吨位;
- 否则输出 −1。
样例
7 8 6
1 2 3
2 3 5
1 3 4
3 4 6
4 5 2
5 6 7
3 6 8
2 6 9
1 2
4 6
5 1
1 7
6 4
2 5
4
6
4
-1
6
7
提示
样例中,询问 1→2 的最优路线为
$$1\xrightarrow{4}3\xrightarrow{8}6\xrightarrow{9}2,$$
其通行吨位为 min{4,8,9}=4;直接走 132 时,通行吨位只有 3。
询问 4→6 的最优路线为
46386,
而绕行 42576 时,通行吨位只有 2。
港口 7 没有任何候选航道,因此询问 1→7 时输出 −1。
下载正式赛最终版 PDF 题面