#P7018. [2017年成都七中集训]跨越国度
[2017年成都七中集训]跨越国度
跨越国度(country)
题目描述
X星球有 个国家,每个国家的领土是平面上的一个简单多边形,各国公共面积为0,每个国家至少与一个国家相邻。全部领土的并集也是简单多边形,并集以外的地区不属于任何国家。输入以全部顶点和线段描述这些领土的分布。
共有 个民族,每个国家由其中一个民族统治。相邻国家的公共边是国界,其权值 表示跨越费用; 表示不能跨越该边。保证任意两个国家之间存在唯一一条可以跨越国界的路径。路径费用为经过的国界权值之和。
两个统治民族相同的国家可以进行友好往来,费用为它们之间上述唯一路径的费用。
现在需要支持将某个国家的统治民族修改为给定民族,并求全部同民族国家对中最小的往来费用。如果不存在两个统治民族相同的国家,输出 。
输入按顺时针给出某个国家的两条相邻边的编号,以该国家的一个角指代这个国家。同一国家可以有不同的指代方式。
输入格式
第一行五个整数 ,依次表示顶点数、线段数、国家数、民族数和修改次数。其中 为正整数, 可为0。
接下来 行,第 行两个正整数,表示编号为 的顶点坐标。
接下来 行,第 行三个整数 ,表示连接顶点 、权值为 的第 条边。所有边仅在顶点处相交。
接下来 行,描述每个国家的初始统治民族。每行三个正整数,前两个数按顺时针给出该国家两条相邻边的编号,第三个数为统治民族编号。
最后 行描述修改操作,格式相同:前两个数指代国家,第三个数为修改后的统治民族。
边的编号为 ,民族编号为 。
输出格式
输出 行,依次表示初始状态及每次修改后的最小往来费用。
样例输入1
6 8 3 3 2
6 7
4 4
8 4
2 1
6 1
10 1
1 2 -1
1 3 -1
2 4 -1
2 5 5
3 5 8
3 6 -1
4 5 -1
5 6 -1
2 1 1
4 3 2
6 5 3
8 6 1
3 7 1
样例输出1
-1
8
5
样例解释

初始有A、B、C三个国家,统治民族各不相同。只有A与B、A与C之间的国界可以跨越,费用分别为5、8。
- 初始没有同民族的两个国家,答案为 。
- 第一次修改后,C与A的统治民族相同,答案为8。
- 第二次修改后,三个国家统治民族相同,答案为5。
数据范围
| 测试点 | 民族数 上界 | 国家数 上界 | 修改次数 限制 | 附加条件 |
|---|---|---|---|---|
| 1—2 | 各国领土均为边平行于坐标轴的矩形 | |||
| 3—4 | 无 | |||
| 5 | 各国领土均为边平行于坐标轴的矩形 | |||
| 6 | 无 | |||
| 7 | 各国领土均为边平行于坐标轴的矩形 | |||
| 8 | 无 | |||
| 9 | 各国领土均为边平行于坐标轴的矩形 | |||
| 10 | 无 | |||
| 11 | 各国领土均为边平行于坐标轴的矩形 | |||
| 12 | 无 | |||
| 13—14 | 各国领土均为边平行于坐标轴的矩形 | |||
| 15—16 | 无 | |||
| 17—18 | 各国领土均为边平行于坐标轴的矩形 | |||
| 19—20 | 无 |
全部数据中,顶点数和边数均不超过国家数的10倍,坐标不超过10000。国界费用为 或不超过10000的正整数。