P1967 [NOIP 2013 Senior] Truck Transportation

NOIP 2013 Senior D1T3.

Country A has $n$ cities, numbered from $1$ to $n$, and there are $m$ bidirectional roads between the cities. Each road has a weight limit for vehicles, referred to as the load limit. There are $q$ trucks transporting goods. The drivers want to know, without exceeding any road's weight limit, the maximum weight each truck can carry.

The first line contains two integers $n,m$ separated by a single space, indicating that Country A has $n$ cities and $m$ roads. Each of the next $m$ lines contains three integers $x, y, z$, separated by single spaces, indicating there is a road from city $x$ to city $y$ with weight limit $z$. Note: $x \neq y$, and there may be multiple roads between two cities. The next line contains an integer $q$, meaning there are $q$ trucks that need to transport goods. Then follow $q$ lines, each containing two integers $x,y$ separated by a space, indicating a truck needs to transport goods from city $x$ to city $y$, with $x \neq y$ guaranteed.

Output $q$ lines, each with an integer, indicating the maximum load for each truck. If a truck cannot reach the destination, output $-1$.

For $30\%$ of the testdata, $1 \le n < 1000$, $1 \le m < 10,000$, $1\le q< 1000$. For $60\%$ of the testdata, $1 \le n < 1000$, $1 \le m < 5\times 10^4$, $1 \le q< 1000$. For $100\%$ of the testdata, $1 \le n < 10^4$, $1 \le m < 5\times 10^4$, $1 \le q< 3\times 10^4 $, $0 \le z \le 10^5$. Translated by ChatGPT 5