1518 . Problem H. 邁向強者之路！
TopCoder
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
1 2 3
2 3 4
3 1 3
1 1 3
2 1 3
1 1 3
Sample Output 1
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 |