有一種人,和凡人不同,擁有著難不倒的高強的智慧,或者是面對重重困難都能隨機應變的靈巧,也可能是有一身非凡的破壞力(?),
這類傑出的人我們稱之為「強者」,以凸顯其地位,就如同我們稱一些人為「ACE」或「Striker」一樣。
然而大家都想成為強者,但是強者之路可是困難重重啊!
你必須從基礎開始,經過一點一滴的累積、經過歲月的歷程,才能夠一步一步的朝著成為強者這個目標邁進。
然而,凡事都不能可能如此順遂,過程中或多或少會有失敗或遭遇到前所未見的困難,因此,到最後能被稱做「強者」的人,實在是少之又少。
就在最近,和野(Kazuno)聽說了在某個國境之南的地方,有一處強者修練區域(The SHIK area),於是他想盡了辦法終於得到了那個區域的地圖。
現在和野手上有一張上頭標示著 N 個練功區(編號1~N) 和 M 條雙向道的強者修煉地圖,
每條路上都有一位鎮關者(Protecter),如果想要安全通過這條路的話自身能力至少要跟鎮關者一樣威!
為了讓和野能順利的前往各個能夠增強能力的地方,現在有個問題需要身為大好人的你來解決:
「和野想要從練功點A安全移動到練功點B,和野至少要有多威才有可能達成?」
然而世界沒有你想像中的美好,鎮關者的老大身上有一種靈丹妙藥, 一旦吃下這種藥的鎮關者將會化身為黑暗大法師,無限超級威…!(Infinity!!) 如果遇到這種鎮關者就只能繞道而行了。 |
|
第一行有三個整數 N(1<=N<=1000),M(1<=M<=100000),和依序發生的事件數K(K<=100000)
接下來M行,每行有三個整數 A, B, C,代表 A, B 之間有一條鎮關者威度為 C 雙向道,
接下來K行,每行有三個整數 T, P, Q
》T=1: 詢問你若要從 P到Q 至少要有多威?
》T=2: 鎮關者老大不高興了!!他餵了位於道路 (P,Q) 上的鎮關者吃下了靈丹妙藥!
對於每個詢問輸出一行,包含一個數字 W 代表至少要有多威。
我們保證修煉地圖中的每個練功地點之間,都一定至少有一條路徑可以到達,且靈丹妙藥數量有限(<=5000)
※敘述友情贊助 - skyly
※主角名稱贊助 - hallogameboy
原TIOJ1518 / Problem Setter: shik
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 10 |
2 | 1 | 10 |
3 | 2 | 10 |
4 | 3 | 10 |
5 | 4 | 10 |
6 | 5 | 10 |
7 | 6 | 10 |
8 | 7 | 10 |
9 | 8 | 10 |
10 | 9 | 10 |