题目描述

Farmer John has recently been experimenting with cultivating different types of grass on his farm, realizing that different types of cows like different types of grass. However, he must be careful to ensure that different types of grass are planted sufficiently far away from each-other, in order to prevent them from being inextricably mixed.

FJ's farm consists of $N$ fields ($1 \leq N \leq 200,000$), where $M$ pairs of fields are connected by bi-directional pathways ($1 \leq M \leq 200,000$). Using these pathways, it is possible to walk from any field to any other field. Each pathway has an integer length in the range $1 \ldots 1,000,000$. Any pair of fields will be linked by at most one direct pathway.

In each field, FJ initially plants one of $K$ types of grass ($1 \leq K \leq N$). Over time, however, he might decide to switch the grass in some field to a different type. He calls this an "update" peration. He might perform several updates over the course of time, which are all cumulative in nature.

After each update, FJ would like to know the length of the shortest path between two fields having different grass types. That is, among all pairs of fields having different grass types, he wants to know which two are closest. Ideally,

this number is large, so he can prevent grass of one type from mixing with grass of another type. It is guaranteed that the farm will always have at least two fields with different grass types.

In 30 percent of the input cases, each field will be directly connected to at most 10 pathways.

输入格式

The first line of input contains four integers, $N$, $M$, $K$, and $Q$, where $Q$ is the number of updates ($1 \leq Q \leq 200,000$).

The next $M$ lines describe the paths; each one contains three integers $A$, $B$, and $L$, indicating a path from field $A$ to field $B$ (both integers in the range $1 \ldots N$) of length $L$.

The next line indicates the initial type of grass growing in each field ($N$ integers in the range $1 \ldots K$).

Finally, the last $Q$ lines each describe an update, specified by two integers $A$ and $B$, where the grass in field $A$ is to be updated to type $B$.

输出格式

For each update, print the length of the shortest path between two fields with different types of grass, after the update is applied.

题目大意

农夫约翰最近一直在在他的农场试种各种类型的草，他发现不同类型的牛，喜欢不同类型的草。然而，他必须注意，在种草时，不同类型的草，要保持足够远的距离，以防止它们混合。他的农场由总共 $N(1\le N\le 2\times 10^5)$ 块田地组成，其中有 $M(1\le M\le 2\times 10^5)$ 对田地中用小路连接。通过这些小路，这些田地联通。每条路的长度在 $[1,10^6]$ 范围内。没有重边。
对于每个田地，草的品种是 $K$ 种草 $(1\le K\le N)$ 中的一种。然而，随着时间的推移，他可能决定在某些田地将草转变为不同品种，称之为“更新”。他可能会在一段时间内执行多次更新，这些更新都是累积的。
在每次更新之后，他想知道具有不同草品种的两个田地之间的最短路径的长度。也就是说，在具有不同草品种的所有田地中，他想知道哪两个是最接近的。保证农场将总是具有至少两个具有不同草品种的田地。

输入格式

第一行输入四个整数 $N,M,K,Q$，$Q$ 代表“更新”的次数。

接下来 $M$ 行，输入三个整数 $A,B,L$，代表一条从 $A$ 到 $B$ 的长度为 $L$ 的双向边。

下一行输入 $N$ 个数，每个数代表这块田地一开始种的哪种草（在 $1\cdots K$）范围内。

最后输入 $Q$ 行，每行两个整数 $A,B$ 表示第 $A$ 块田地的草被换成了第 $B$ 品种。

输出格式

总共有 $Q$ 行，每行一个整数。

每个更新后，输出不同种类草之间的最短距离。

数据范围

$1\le N,M,Q\le 2\times 10^5,1\le K\le N$。

对于所有边，有 $1\le A,B\le N,1\le L\le 10^6$。

对于 30% 的数据，保证每个田地衍生出来的道路条数 $\le 10$。

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

提示

感谢 @∑∵∴∷ 的翻译。

简洁翻译 by cc123321 :

给定一张带权无向图，每个点有一个颜色，每次改变一个点的颜色，要求你在操作后输出这个图中最近异色点对之间的距离。最近异色点对定义为：一对点颜色不同，且距离最小。