#SYUCT13M. 冰洋航道

冰洋航道

题目描述

极夜降临,冰洋上的 nn 座港口被浮冰封锁,编号依次为 1,2,…,n1,2,\ldots,n。

勘测队标出了 mm 条候选航道。第 ii 条航道双向连接港口 uiu_i 与 viv_i(ui≠viu_i\ne v_i),其安全吨位为 wiw_i。一艘船通过该航道时,排水量不能超过 wiw_i。

一支船队可以选择任意一条从港口 ss 到港口 tt 的路线航行(s≠ts\ne t)。一条路线由一条或多条首尾相接的候选航道组成,同一座港口或同一条航道都可以重复经过。

设路线 PP 经过的航道编号依次为 e1,e2,…,eke_1,e_2,\ldots,e_k,则它的通行吨位定义为

cap⁡(P)=min⁡1≤j≤kwej.\operatorname{cap}(P)=\min_{1\le j\le k}w_{e_j}.

对于每次询问 (s,t)(s,t),请在所有从 ss 到 tt 的路线中最大化通行吨位,即求

max⁡P:s⇝tcap⁡(P).\max_{P:s\leadsto t}\operatorname{cap}(P).

如果不存在从 ss 到 tt 的路线,则输出 −1-1。

输入格式

第一行输入三个整数 n,m,qn,m,q(2≤n≤2×1052\le n\le 2\times 10^5,0≤m≤2×1050\le m\le 2\times 10^5,1≤q≤2×1051\le q\le 2\times 10^5),分别表示港口数、候选航道数和询问数。

接下来 mm 行,第 ii 行输入三个整数 ui,vi,wiu_i, v_i, w_i(1≤ui,vi≤n1\le u_i, v_i\le n,ui≠viu_i\ne v_i,1≤wi≤1091\le w_i\le 10^9),表示一条连接 uiu_i 与 viv_i、安全吨位为 wiw_i 的候选航道。两座港口之间可能有多条航道。

接下来 qq 行,每行输入两个整数 s,ts, t(1≤s,t≤n1\le s, t\le n,s≠ts\ne t),表示一次询问。

输出格式

输出 qq 行。第 ii 行输出一个整数:

  • 如果第 ii 次询问中的两个港口连通,输出它们之间的最大通行吨位;
  • 否则输出 −1-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→21\to 2 的最优路线为

$$1\xrightarrow{4}3\xrightarrow{8}6\xrightarrow{9}2,$$

其通行吨位为 min⁡{4,8,9}=4\min\{4,8,9\}=4;直接走 1→321\xrightarrow{3}2 时,通行吨位只有 33。

询问 4→64\to 6 的最优路线为

4→63→86,4\xrightarrow{6}3\xrightarrow{8}6,

而绕行 4→25→764\xrightarrow{2}5\xrightarrow{7}6 时,通行吨位只有 22。

港口 77 没有任何候选航道,因此询问 1→71\to 7 时输出 −1-1。

下载正式赛最终版 PDF 题面