P14912 [NHSPC 2024] 海盜地圖

在某個大洋中，有 $n$ 座小島，分別編號從 $\{1, 2, \ldots, n\}$，另外也有著 $m$ 條航線來直接連接兩個小島。每條航線都以一組數字 $x, y$ 表示 ，代表透過這條航線從小島 $x$ 行船至小島 $y$ 只需要一單位的時間，反之從小島 $y$ 行船至小島 $x$ 也只需要一單位的時間。然而並不是任兩個小島 $x$ 和 $y$ 都有一條航線直接連接，這時要從 $x$ 行船至 $y$，需要透過一系列的小島作為中間接駁的島。具體來說，我們需要一系列的小島 $a_1, a_2, \ldots, a_k$，其中 $x = a_1,y = a_k$，而且對於所有 $1 \leq i \leq k-1$，$a_i$ 和 $a_{i+1}$ 有航線直接相連，這會是一個間接連接小島 $x$ 和 $y$ 的方式，並且需要花費 $k-1$ 單位的時間。兩個小島之間的最快速行船路線的所需時間為所有能滿足上列要求的序列所需花費時間的最小值。並且任意兩個小島都能透過這些航線直接或間接的連接。 另外在每座小島都有一組海盜佔據著，他們各自紀錄著從他們所在的小島至各個島的最快速行船路線的所需時間。由於海盜們十分忙碌，有些需要花費比較長時間的行船路線，會隨著時間的過去，而忘記確切的所需時間。只能確定這些被遺忘的最快速行船路線的所需時間的值**至少嚴格大於 $\sqrt{n}$。** :::align{center}  圖片來源：產生自 ChatGPT ::: 海盜們將航線的完整資訊寄給你，並給 $q$ 組被遺忘的路線，希望你幫他們算出這些已忘記的最快速行船路線的所需時間。

$$\begin{aligned} &n \ m \ q \\ &x_1 \ y_1 \\ &x_2 \ y_2 \\ &\vdots \\ &x_m \ y_m \\ &s_1 \ t_1 \\ &s_2 \ t_2 \\ &\vdots \\ &s_q \ t_q \end{aligned}$$ * $n$ 代表小島數。 * $m$ 代表海盜給出的航線數。 * $q$ 代表忘記所需時間的最快速行船路線數量。 * $x_i, y_i$ 代表有一條航線直接連接著小島 $x_i$ 和 $y_i$。 * $s_i, t_i$ 代表海盜遺忘的第 $i$ 條路線。

$$\begin{aligned} d_1 \ d_2 \ \ldots \ d_q \end{aligned}$$ * $d_i$ 代表海盜遺忘的第 $i$ 條路線所需的最快速行船時間。

### 測資限制 * $1 \leq n \leq 10^4$。 * $1 \leq m \leq 10^5$。 * $1 \leq q \leq 3\times 10^4$。 * $1 \leq x_i, y_i \leq n,x_i \neq y_i$。 * $1 \leq s_i, t_i \leq n$。 * 保證所有被遺忘的路線皆滿足其最快速行船路線的所需時間的值**至少嚴格大於 $\sqrt{n}$。** * 海盜給出的航線都是相異的。 * 保證任意兩個小島都能透過這些航線直接或間接的連接。 * 輸入的數皆為整數。 ### 評分說明 本題共有四組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。 | 子任務 | 分數 | 額外輸入限制 | | :------: | :----: | ------------ | | 1 | 6 | $n \le 500$。 | | 2 | 17 | $n \le 5\times 10^3$，$m \le 10^4$。 | | 3 | 21 | 詳見備註（一）。 | | 4 | 56 | 無額外限制。 | 備註（一）：存在至多 $1000$ 個特別小島，使得所有被遺忘的從小島 $x$ 至小島 $y$ 最快速行船路線的所需時間，不是 $x$ 是特別小島，就是 $y$ 是特別小島。