k188. pE. 公路 (road) - 高中生程式解題系統

內容

題目敘述 : https://drive.google.com/file/d/1nDZNGCptQGcAZDxqRGcNt_wpz31clODZ/view?usp=sharing

某國的公路網由 $n$ 個城鎮(編號 $1$ ∼ $n$ )和 $m$ 條連接兩個相異城鎮的雙向公路組成，每條公路有其長度，以公里表示。最近該國流行起電動車，但是公路之間都沒有充電站，電動車只能在城鎮充電。該國交通部門官員十分擔心有些被觀光局規劃好的旅程會使電動車的續航力沒辦法走完一條公路，也因此，官員希望旅程中使用到的最長公路長度要盡量短，否則若有些電動車的實際續航力低於一段公路的長度，它們一定會在公路中間沒電。

對於一趟被規劃好的旅程，觀光局會為其決定好一個起點 $u$ 和終點 $v$ ，並找出兩條由 $u$ 到 $v$ 公路相互不重複的路徑，來做為一個完整的旅程規劃。例如下圖是一個 $n = 7$ 、 $m = 9$ 的例子，點上標示城鎮的編號，邊上標示公路的長度。

若要規劃城鎮 1 到城鎮 2 的旅程，可以採用以下兩條路徑：
• 1 → 2 以及 1 → 3 → 2

這兩條路徑中，所使用的到的最長公路長度是 8 公里，但若採用以下兩條路徑：
• 1 → 2 以及 1 → 3 → 5 → 2
就可以將使用的最長公路長度降低至 5，也是使最長公路最短的選擇方式。而若要規劃城鎮 1 到城鎮 6 的旅程，可以採用以下兩條路徑：
• 1 → 3 → 6 以及 1 → 2 → 5 → 3 → 4 → 6

使用的最長公路長度是 7，同時也是使最長公路最短的選擇方式，注意到雖然這兩條路徑共用了同一個城鎮 3，但條件只要求「使用的公路不重複」，因此為一種滿足條件的路徑選擇方式。
一個旅程的兩條路徑所使用的最長公路愈短，則該旅程愈佳。今給定 $q$ 對起終點，請寫程式計算每對起終點之最佳旅程使用到的最長公路長度，或者回報不存在任何一種路徑的選擇方式。

測資限制

• $2 \leq n \leq 1000$ 。
• $n - 1 \leq m \leq \frac{n \times (n - 1)}{2}$ 。

• $1 \leq a_{i}, b_{i} \leq n$ , $a_{i} \neq b_{i}$ 。
• $1 \leq l_{i} \leq 10^{9}$ 。
• 不會有兩條公路連接著相同的一組城鎮。
• $1 \leq q \leq 5 \times 10^{5}$ 。
• $1 \leq u_{i}, v_{i} \leq n$ , $u_{i} \neq v_{i}$ 。
• 輸入的數皆為整數。
• 保證任兩個城鎮可以透過若干條公路直接或間接抵達。

輸入說明

n

m

a_{1}

b_{1}

l_{1}

a_{2}

b_{2}

l_{2}

...

a_{m}

b_{m}

l_{m}

q

u_{1}

v_{1}

u_{2}

v_{2}

...

u_{q}

v_{q}

• $n$ , $m$ 分別代表城鎮和公路的數量。
• 第 $i$ 條公路連接著城鎮 $a_{i}$ 和 $b_{i}$ ，且長度為 $l_{i}$ 公里。
• $q$ 代表預計規劃的旅程數量。
• 第 $i$ 個旅程預計選擇 $u_{i}$ 作為起點、 $v_{i}$ 作為終點。

輸出說明

p_{1}

p_{2}

...

p_{q}

• $p_{i}$ 為一整數
– 若 $p_{i}$ $=$ $- 1$ ，則表示不存在路徑的選擇方法可以完整的規劃第 $i$ 個旅程。
– 否則， $p_{i}$ 代表在最佳的路徑選擇方式下，第 $i$ 個旅程所使用到的最長公路長度最小值。

範例輸入 #1

範例輸出 #1

5
7
-1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (3%): 2.0s , <1K
公開測資點#1 (3%): 2.0s , <1M
公開測資點#2 (4%): 2.0s , <1M
公開測資點#3 (4%): 2.0s , <1M
公開測資點#4 (4%): 2.0s , <1M
公開測資點#5 (6%): 2.0s , <1M
公開測資點#6 (6%): 2.0s , <1M
公開測資點#7 (6%): 2.0s , <1M
公開測資點#8 (6%): 2.0s , <1M
公開測資點#9 (7%): 2.0s , <1M
公開測資點#10 (4%): 2.0s , <10M
公開測資點#11 (4%): 2.0s , <10M
公開測資點#12 (4%): 2.0s , <10M
公開測資點#13 (5%): 2.0s , <10M
公開測資點#14 (5%): 2.0s , <10M
公開測資點#15 (5%): 2.0s , <10M
公開測資點#16 (6%): 2.0s , <50M
公開測資點#17 (6%): 2.0s , <50M
公開測資點#18 (6%): 2.0s , <10M
公開測資點#19 (6%): 2.0s , <10M

提示：

題目和測資來源 : twpca

注意因為礙於系統問題測試資料沒辦法完整的放上來，時間限制也跟原本有出入(因本judge常數較大有調整)

子任務	分數	額外輸入限制	測資點
1	18	$n \leq 100,$ $m, q \leq 300,$ $l_{i} = 1$	#00~#04
2	31	$n \leq 500,$ $m, q \leq 1000$	#05~#09
3	22	$m \leq 3000$	#10~#14
4	29	無額外限制	#15~#19

如果題目有問題歡迎來信詢問!

標籤:

BCC tarjan 二分搜尋法圖論離線算法

出處:

TOI入營考 2023 [管理者： Ststone1687 (Ststone) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」