#1648. 圣杯战争

圣杯战争

题目描述

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

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

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

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

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

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

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

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

输入格式

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

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

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

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

输出格式

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

样例

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%20\% 的数据,1n,m103,1K103,1Q1001\le n,m\le 10^3,1\le K\le 10^3,1\le Q\le 100

对于 40%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%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%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$。

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

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