動態規劃

題目敘述

你是個喜歡藉由免費擁抱來散播愛的熊頭。

每天你都會去一座能到達的城市，舉免費擁抱的牌子，為這個社會帶來一些溫暖。

有些城市與城市之間會有高鐵，想從一座城市去到另外一座城市一定得藉由搭高鐵。而從城市搭高鐵到另一座城市都需要花錢買票才可以搭乘高鐵。往返於兩座城市之間的高鐵票價一定是相同的。

你平常都住在熊頭洞穴裡(雖然叫洞穴但當然也在城市裡)。熊頭洞穴可能不只有一個，但一座城市最多只會有一個熊頭洞穴。熊頭洞穴裡面都有傳送門，讓你可以從任意洞穴瞬間移動到任意一個洞穴，不需要花費任何錢。

你在每座城市舉牌子都能夠為社會帶來一些溫暖度，而有時舉牌子能帶來的溫暖度是會改變的。

你每天都會從熊頭洞穴出門(有傳送門，想從哪個熊頭洞穴出門都可以)，並攜帶一些交通費，接著挑選一座能夠帶來最大溫暖度的城市去舉牌子。搭乘高鐵不能花超過你攜帶的交通費(不用擔心回程的問題，高鐵購票都有免費附回程票)。

你出門前得好好地規劃行程，因為攜帶的交通費及在城市舉牌能帶來的溫暖度不一定每趟旅程都一樣，所以目的地也不總會是一樣的，因此行程的規劃得是動態的才行！

輸入說明

第一行有兩個整數$V(1\leq V\leq 10^4)$和$E(1\leq E\leq$ min$\{10^5,\frac{V*(V-1)}{2}\})$，表示城市的數量與有幾組城市之間是有高鐵的。城市編號由$1$到$V$。

第二行有$V$個整數$a_1,a_2,a_3...a_V(0\leq |a_i|\leq 10^5)$，分別表示在第$i$座城市舉牌能帶來的溫暖度。

接著有$E$行，每行給定三個整數$u,v,c(1\leq u,v\leq V,u\neq v,1\leq c\leq 10^5)$，表示可以花費$c$元買車票，往返於城市$u$與城市$v$之間。

再來有一個整數$N(1\leq N\leq V)$，表示熊頭洞穴的數量。

然後有$N$個整數$S_1,S_2,S_3...S_N(1\leq S_i\leq V)$，表示熊頭洞穴分別在哪幾座城市。

再來有一個整數$Q(1\leq Q\leq 10^5)$，表示有$Q$筆事件。

接著$Q$行，每行先給定一個整數$t(1\leq t\leq 2)$，表示事件類型；若$t=1$，接著會有兩個整數$p(1\leq p\leq V)$與$v(0\leq |v|\leq 10^5)$，表示在第$p$座城市舉牌能帶來的溫暖度變更為$v$；若$t=2$，則會有一個整數$k(1\leq k\leq 10^9)$，表示你打算攜帶$k$元的交通費出門舉牌。

輸出說明

對於每次出門舉牌，輸出一個整數，表示在目的地城市舉牌能為社會帶來的溫暖度，輸出後換行。

範例輸入

7 7
15 2 8 5 4 7 1
1 2 10
2 3 7
2 4 3
3 5 4
4 5 5
5 6 4
5 7 2
2
2 7
6
2 1
2 3
2 6
2 87
1 6 10
2 6

範例輸出

子任務

子任務一($5\%$)：$E=V-1$、$V,Q\leq 500$、相鄰編號的城市之間必有高鐵且車票費用皆為$1$元、熊頭洞穴只有一個且位於城市$1$裡。
子任務二($10\%$)：$E=V-1$、相鄰編號的城市之間必有高鐵且車票費用皆為$1$元、熊頭洞穴只有一個、城市舉牌能帶來的溫暖度不會改變。
子任務三($20\%$)：$E=V-1$、相鄰編號的城市之間必有高鐵、熊頭洞穴只有一個。
子任務四($10\%$)：$Q\leq 50$且熊頭洞穴只有一個。
子任務五($20\%$)：$Q\leq 50$。
子任務六($35\%$)：無限制

提示

付錢就可以免費拿到回程票

Judge Setting

run-time limit: 1000 ms
memory limit: 538443776 byte
測資數量: 25