TopCoder

willychan
$\huge{施~~竣~~耀~~}$

User's AC Ratio

40.0% (2/5)

Submission's AC Ratio

10.0% (2/20)

Tags

Description

有一種人,和凡人不同,擁有著難不倒的高強的智慧,或者是面對重重困難都能隨機應變的靈巧,也可能是有一身非凡的破壞力(?),
這類傑出的人我們稱之為「強者」,以凸顯其地位,就如同我們稱一些人為「ACE」或「Striker」一樣。

然而大家都想成為強者,但是強者之路可是困難重重啊!
你必須從基礎開始,經過一點一滴的累積、經過歲月的歷程,才能夠一步一步的朝著成為強者這個目標邁進。

然而,凡事都不能可能如此順遂,過程中或多或少會有失敗或遭遇到前所未見的困難,因此,到最後能被稱做「強者」的人,實在是少之又少。

就在最近,和野(Kazuno)聽說了在某個國境之南的地方,有一處強者修練區域(The SHIK area),於是他想盡了辦法終於得到了那個區域的地圖。

現在和野手上有一張上頭標示著 N 個練功區(編號1~N) 和 M 條雙向道的強者修煉地圖,
每條路上都有一位鎮關者(Protecter),如果想要安全通過這條路的話自身能力至少要跟鎮關者一樣威!

為了讓和野能順利的前往各個能夠增強能力的地方,現在有個問題需要身為大好人的你來解決:

「和野想要從練功點A安全移動到練功點B,和野至少要有多威才有可能達成?」

然而世界沒有你想像中的美好,鎮關者的老大身上有一種靈丹妙藥, 一旦吃下這種藥的鎮關者將會化身為黑暗大法師,無限超級威…!(Infinity!!) 如果遇到這種鎮關者就只能繞道而行了。

             

Input Format

第一行有三個整數 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) 上的鎮關者吃下了靈丹妙藥!

Output Format

對於每個詢問輸出一行,包含一個數字 W 代表至少要有多威。

Sample Input 1

3 3 3
1 2 3
2 3 4
3 1 3
1 1 3
2 1 3
1 1 3

Sample Output 1

3
4

Hints

我們保證修煉地圖中的每個練功地點之間,都一定至少有一條路徑可以到達,且靈丹妙藥數量有限(<=5000)

※敘述友情贊助 - skyly
※主角名稱贊助 - hallogameboy

Problem Source

原TIOJ1518 / Problem Setter: shik

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 5000 65536 262144 8
8 5000 65536 262144 9
9 5000 65536 262144 10