P1119 Post-disaster Reconstruction

B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。

Given the number of villages $N$ in Region B, numbered from $0$ to $N-1$, and the lengths of all $M$ bidirectional roads. For each village $i$, you are given the day it is completed $t_i$. All reconstructions start simultaneously, and village $i$ is completed on day $t_i$, becoming open to traffic on that day. If $t_i$ is $0$, the earthquake did not damage that village and it is open from the beginning. Then there are $Q$ queries $(x,y,t)$. For each query, answer the length of the shortest path from village $x$ to village $y$ on day $t$. If there is no path from $x$ to $y$ using only villages that have been completed by day $t$, or if village $x$ or village $y$ has not been completed by day $t$, output $-1$.

- The first line contains two positive integers $N,M$, the number of villages and the number of roads. - The second line contains $N$ non-negative integers $t_0,t_1,\cdots,t_{N-1}$, the completion day of each village, and it is guaranteed that $t_0 \le t_1 \le \cdots \le t_{N-1}$. - The next $M$ lines each contain three non-negative integers $i,j,w$ with $w \le 10000$, indicating a road between villages $i$ and $j$ with length $w$. It is guaranteed that $i \ne j$, and for any pair of villages there is at most one road. - The next line contains a positive integer $Q$, the number of queries. - The next $Q$ lines each contain three non-negative integers $x,y,t$, asking for the shortest path length from village $x$ to village $y$ on day $t$. It is guaranteed that $t$ is non-decreasing across the queries.

Output $Q$ lines. For each query $(x,y,t)$, output the corresponding answer: the length of the shortest path from village $x$ to village $y$ on day $t$. If on day $t$ there is no path from $x$ to $y$ using only villages that have been completed by day $t$, or if village $x$ or village $y$ has not been completed by day $t$, output $-1$.

- For $30\%$ of the testdata, $N \le 50$. - For $30\%$ of the testdata, $t_i=0$; among them, for $20\%$ of the testdata, $t_i=0$ and $N>50$. - For $50\%$ of the testdata, $Q \le 100$. - For $100\%$ of the testdata, $1 \le N \le 200$, $0 \le M \le \dfrac{N\times(N-1)}{2}$, $1 \le Q \le 50000$, and all integers in the input are at most $10^5$. Translated by ChatGPT 5