Skip to content

1090: Bang

题目

题目描述

范细榜和金之榜是好朋友。他们住在一个盛产膀的国家,该国有N个城市,第i个城市的膀资源丰富度为W_i。并且该国交通十分发达,所有城市通过M条双向公路联通,并且从一个城市出发到达该国家的任何一个城市。

有时候他们两个会决定一起去买膀。范细榜从城市B出发,金之榜从城市C出发。他们每天可以且必须从一个城市移动到其相邻的城市。他们甚至可以到之前去过的城市。经过X天后(X为任意非负整数,且由两人自行决定),他们最终决定停留在那座城市买膀(两人最后可以在同一城市)。由于二人关系很好,所以为了顾及对方感情,他们觉得他们最后所停留的城市膀资源丰富度的差要尽可能小,否则可能一个会超巨膀,一个会变成超细膀。他们想知道,这个差最小是多少?

同时有时候,膀资源也会发生变动,在特定时候城市P的膀资源会变成Q。

输入格式

第一行两个整数N,M,如题意。

第二行N个数W_1 ... W_N,表示这些城市的初始膀资源分布。

接下来M行,每行两个数a_i,b_i,表示城市a_i与b_i毗邻。

再一行一个数字Q,表示接下来会发生Q件事。

紧接着Q行,每行三个数A_i,B_i,C_i。

  • 若A_i = 0,表示这时城市B_i的膀资源丰富度变为了C_i。

  • 若A_i = 1,表示这时范细膀和金之榜决定外出买膀,一个从B_i城市出发,一个从C_i城市出发。

输出格式

对于每个A_i=1的操作,输出一行,包含一个最小差值。

样例输入

6 6 
0 0 0 0 0 0 
1 2
1 6
5 1
2 3
3 4
3 5
7
1 1 2
0 1 10
0 3 20 
1 1 2
0 4 11 
1 1 3 
1 1 6

样例输出

0
10 
0 
1

数据范围

对于10%的数据,N ≤ 10,M ≤ 20,Q ≤ 10。

对于20%的数据,N ≤ 100,M ≤ 200,Q ≤ 100。

对于30%的数据,N ≤ 1000,M ≤ 2000,Q ≤ 1000。

对于40%的数据,N ≤ 1000,M ≤ 200000,Q ≤ 1000。

对于另外10%的数据,A_i=1。

对于100%​的数据,N ≤ 100000,M ≤ 200000,Q ≤ 100000,W_i,C_i ≤ 10^9。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!