P9235 [Lanqiao Cup 2023 NOI Qualifier A] Network Stability

There is a local area network consisting of $n$ devices and $m$ physical connections. The stability of the $i$-th connection is $w_i$. For a path from device $A$ to device $B$ that passes through several physical connections, we define the stability of this path as the minimum stability among all connections on the path. We define the communication stability between device $A$ and device $B$ as the maximum stability among all feasible paths from $A$ to $B$. Given the physical connection information in the LAN, compute the communication stability for several pairs of devices $x_i$ and $y_i$. If there is no path between two devices, output $-1$.

The first line contains three integers $n, m, q$, representing the number of devices, the number of physical connections, and the number of queries. The next $m$ lines each contain three integers $u_i, v_i, w_i$, meaning there is a physical connection between $u_i$ and $v_i$ with stability $w_i$. The next $q$ lines each contain two integers $x_i, y_i$, asking for the communication stability between $x_i$ and $y_i$.

Output $q$ lines. Each line contains one integer, in order, representing the answer to each query.

[Scale and constraints of testdata] For $30\%$ of the testdata, $n, q \leq 500$, $m \leq 1000$. For $60\%$ of the testdata, $n, q \leq 5000$, $m \leq 10000$. For all testdata, $2 \leq n, q \leq 10^5$, $1 \leq m \leq 3 \times 10^5$, $1 \leq u_i, v_i, x_i, y_i \leq n$, $1 \leq w_i \leq 10^6$, $u_i \neq v_i$, $x_i \neq y_i$. Translated by ChatGPT 5