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" operation. 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.

Problem credits: Lewin Gan

Problem credits: Lewin Gan

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.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > US Open > Platinum