#6541. 圣杯战争

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

原题来自 USACO 2017 US Open Contest, Platinum Problem 2. Switch Grass,数据范围有改动。

「这场圣杯战争……从一开始,就很不对劲。」

由于这场圣杯战争过于异常,作为中立调停的「裁定者」贞德被大圣杯召唤。

圣杯战争在 n 座城市内进行,这些城市之间通过 m 条路径相互连接彼此可以相互到达,由于某些特殊规则,所有的从者只能通过这 m 条路径从一个城市到达另一个城市。开始时,每个城市都会出现有且仅有一位从者。

令贞德不安的是,从者们既不是各自为战,也没有完整的阵营组合:每位从者分属一个阵营 k_i ,相同阵营的从者之间不会相互攻击,并且所有阵营均没有固定的从者数目。

在混战中,被击杀的从者会直接回归英灵座而消失,退出这场圣杯战争。大圣杯继续召唤一位英灵作为从者,让他/她降临在被击杀的从者所在的城市。

陷入迷惘的贞德整理了思绪,决定先去监督不同阵营的从者之间相距最近的一组战斗(指两个从者到达对方城市的最短距离),并希望知道每次更换(接着上一次的更新进行)了从者后所有战斗的最短距离。请帮助贞德完成这个任务。

大圣杯保证不会只剩下一种阵营。

输入格式

第一行,包含四个整数 n,m,K,Q ,分别表示城市个数,路径条数,本次圣杯战争参战的不同阵营数目,以及更换从者的次数。

接下来 m 行,每行包含三个整数 u,v,w ,表示城市 u,v 之间存在一条长度为 w 的路径。

接下来一行,包含 n 个整数 k_1,k_2,\cdots ,k_n ,表示开始时每个城市召唤的从者所属阵营。

接下来 Q 行,每行包含两个整数 x,k ,表示城市 x 重新召唤了所属阵营为 k 的从者。

输出格式

对于每一次从者更换,输出一行包含一个整数,表示不同阵营之间战斗的最短距离。

样例

样例输入

3 2 3 4
1 2 3
2 3 1
1 1 2
3 3
2 3
1 2
2 2

样例输出

1
3
3
1

数据范围与提示

对于 20\% 的数据, 1\le n,m\le 10^3,1\le K\le 10^3,1\le Q\le 100

对于 40\% 的数据, 1\le n\le 5\times 10^3,1\le m\le 10^4,1\le K\le 10^6,1\le Q\le 10^4

对于 60\% 的数据, 1\le n\le 2\times 10^4,1\le m\le 4\times 10^4,1\le K\le 10^6,1\le Q\le 10^4

对于 100\% 的数据, 1\le u,v,x\le n\le 2\times 10^5,1\le m\le 4\times 10^5,1\le k\le K\le 10^6,1\le Q\le 2\times 10^5,1\le w\le 10^6

最后四组数据中保证存在一组数据,每座城市最多只有 10 条路径连向其他城市。

当前的更改是在完成前面所有更改的前提下继续的。