藉由你的協助,喵喵成功決定了旅遊目的地,並且前往「可以玩最久的縣市」。然而,在抵達之後,他發現他之前蒐集到的資料只包含了主要幹道,其實該縣市當中還有更多連接兩相異鄉鎮、錯綜複雜的小路,當然,每一條仍然都是雙向道,而任兩個鄉鎮之間最多只會有一條直接連接的道路(包含幹道和小路)。
更神奇的是,那個縣市的人民,有時候覺得某些路太好走、有時候又覺得太難走。因此,當地政府不時會進行道路施工。
因為道路施工到底要施工得多難走或多好走有些難管控,於是該縣市為每條路定義了一個「好走度」指標。
為了增加民眾滿意度,當地政府調查了人民來往各地的習慣。結果顯示,所有的人民從鄉鎮A到鄉鎮B的路徑,都不會經過相同的路超過一次。然而,由於這個縣市的人口實在是太多了,為了避免塞車或過於擁擠,每個人都會選擇不一樣的路。
因此,該縣市政府處理人民反應路太好走或太難走的方式如下:政府要求人民反應時要提供他路線的起終點,而施工時,他們會把這組起終點之間人民會走的所有可能路線都進行改造,使這些道路的「好走度」全部加或減某個常數。(注意同一次的施工同一條道路的好走度只會被改變一次。)
簡單來說,每次的道路施工都可以表示為三元組(A, B, K),代表把鄉鎮A到鄉鎮B的所有可能路線經過的所有道路「好走度」全部加上K。(K可能是負數。)
正所謂入境隨俗,喵喵到了這個縣市也決定採取「一個旅程不經過相同的路超過一次」的原則。但是由於擔心遇到太難走的道路,所以他事先擬定了一些兩鄉鎮之間的旅程,想要知道每趟旅程中遇到最難走的道路「好走度」最小可以是多少。由於道路實在太多了,而且道路施工實在太常發生了,好走度隨時都會改變,因此你的任務就是幫喵喵寫出一個程式,可以處理該縣市的所有道路施工,並回答喵喵的問題。
第一行有一個正整數$T$,代表這筆測試資料是屬於哪個子任務。
第二行有三個正整數$N,M,Q$,分別代表該縣市的鄉鎮數量、雙向道數量、道路施工與詢問的總量。
接下來$M$行,每行有三個非負整數$A,B,K$,代表有一條雙向道連接鄉鎮$A,B$,其「好走度」為$K$。
接下來$Q$行,每行代表一個道路施工或一個詢問:
如果是0 A B K,代表道路施工,表示為三元組(A, B, K)。詳細說明請見題目敘述。
如果是1 A B,代表詢問所有從鄉鎮A到鄉鎮B的走法中,遇到最難走的道路「好走度」的最小值。
對於所有測資,$N,M\leq 10^ 5$,$Q\leq 8\times 10^ 4$。
保證所有道路、道路施工或詢問指定的鄉鎮都存在,且詢問或操作的兩鄉鎮必相異。
對於任何時刻任何一條道路的「好走度」K,$|K|\leq 10^ 8$。
子任務(測資) | 額外限制 | 分數 |
1 (0~2) | $N, M, Q\leq 8$ | 17 |
2 (0~5) | $N, Q\leq 2000$ | 46 |
3 (6~8) | 不會有道路施工 | 11 |
4 (9~11) | 至少存在一種方法,可以從鄉鎮0開始恰經過所有幹道和小路一次後回到鄉鎮0(當然會重複經過鄉鎮) | 13 |
5 (12~14) | 只有幹道,沒有小路 | 47 |
6 (0~17) | 無限制 | 66 |
對於每一筆詢問,輸出一行整數代表所要求的答案。
時間寶貴,好吃的小測資記得拿(?
Problem set / Description by Yihda Yol
建國中學105學年度校內第四次模擬賽pF
No. | Testdata Range | Score |
---|---|---|
1 | 0~2 | 17 |
2 | 0~5 | 46 |
3 | 6~8 | 11 |
4 | 9~11 | 13 |
5 | 12~14 | 47 |
6 | 0~17 | 66 |