Switch Grass

提交数: 10, 通过率: 0%, 平均分: 12

题目描述:

Farmer John has recently been experimenting with cultivating different types of grass on his farm, r
ealizing 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 Nfields (1≤N≤200,000), where M pa
irs of fields are connected by bi-directional pathways (1≤M≤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…1,000,000. Any pair of fields will be linked by at most one direct pathway.In each field, FJ init
ially plants one of Ktypes of grass (1≤K≤N). Over time, however, he might decide to switch the gra
ss 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, a
mong all pairs of fields having different grass types, he wants to know which two are closest. Ideal
ly, 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
≤Q≤200,000). The next M lines describe the paths; each one contains three integers A, B, and L, in
dicating a path from field A to field B (both integers in the range 1…N) of length L. The next line
 indicates the initial type of grass growing in each field (N integers in the range 1…K). Finally, 
the last Q lines each describe an update, specified by two integers A and B, where the grass in fiel
d 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.

样例输入:

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
时间限制: 1000ms
空间限制: 128MB

来源: Usaco2017 Open Platinum