TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

33.3% (2/6)

Submission's AC Ratio

9.7% (7/72)

Description

藉由你的協助,喵喵成功決定了旅遊目的地,並且前往「可以玩最久的縣市」。然而,在抵達之後,他發現他之前蒐集到的資料只包含了主要幹道,其實該縣市當中還有更多連接兩相異鄉鎮、錯綜複雜的小路,當然,每一條仍然都是雙向道,而任兩個鄉鎮之間最多只會有一條直接連接的道路(包含幹道和小路)。
更神奇的是,那個縣市的人民,有時候覺得某些路太好走、有時候又覺得太難走。因此,當地政府不時會進行道路施工。
因為道路施工到底要施工得多難走或多好走有些難管控,於是該縣市為每條路定義了一個「好走度」指標。

為了增加民眾滿意度,當地政府調查了人民來往各地的習慣。結果顯示,所有的人民從鄉鎮A到鄉鎮B的路徑,都不會經過相同的路超過一次。然而,由於這個縣市的人口實在是太多了,為了避免塞車或過於擁擠,每個人都會選擇不一樣的路。
因此,該縣市政府處理人民反應路太好走或太難走的方式如下:政府要求人民反應時要提供他路線的起終點,而施工時,他們會把這組起終點之間人民會走的所有可能路線都進行改造,使這些道路的「好走度」全部加或減某個常數。(注意同一次的施工同一條道路的好走度只會被改變一次。)
簡單來說,每次的道路施工都可以表示為三元組(A, B, K),代表把鄉鎮A到鄉鎮B的所有可能路線經過的所有道路「好走度」全部加上K。(K可能是負數。)

正所謂入境隨俗,喵喵到了這個縣市也決定採取「一個旅程不經過相同的路超過一次」的原則。但是由於擔心遇到太難走的道路,所以他事先擬定了一些兩鄉鎮之間的旅程,想要知道每趟旅程中遇到最難走的道路「好走度」最小可以是多少。由於道路實在太多了,而且道路施工實在太常發生了,好走度隨時都會改變,因此你的任務就是幫喵喵寫出一個程式,可以處理該縣市的所有道路施工,並回答喵喵的問題。

Input Format

第一行有一個正整數$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

Output Format

對於每一筆詢問,輸出一行整數代表所要求的答案。

Sample Input

1
3 3 4
0 1 5
1 2 7
2 0 11
0 1 2 -5
1 0 2
0 0 1 10
1 1 2

Sample Output

2
12

Hints

時間寶貴,好吃的小測資記得拿(?

Problem Source

Problem set / Description by Yihda Yol
建國中學105學年度校內第四次模擬賽pF

Subtasks

For Testdata: 0 ~ 2, Score: 17
For Testdata: 0 ~ 5, Score: 46
For Testdata: 6 ~ 8, Score: 11
For Testdata: 9 ~ 11, Score: 13
For Testdata: 12 ~ 14, Score: 47
For Testdata: 0 ~ 17, Score: 66
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 900 131072 262144
1 900 131072 262144
2 900 131072 262144
3 900 131072 262144
4 900 131072 262144
5 900 131072 262144
6 900 131072 262144
7 900 131072 262144
8 900 131072 262144
9 900 131072 262144
10 900 131072 262144
11 900 131072 262144
12 900 131072 262144
13 900 131072 262144
14 900 131072 262144
15 900 131072 262144
16 900 131072 262144
17 900 131072 262144