#20. [CSP-S 2021] 交通规划

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: Sky390

题目描述

给定一个平面上 条水平直线和 条垂直直线,它们相交形成 列的网格,从上到下第 条水平直线和从左到右第 条垂直直线之间的交点称为格点 。网格中任意两个水平或垂直相邻的格点之间的线段称为一条边,每条边有一个非负整数边权。 进行 次询问,每次询问形式如下:

给出 次询问的 可能不同)个附加点,每个附加点位于一条从网格边缘向外出发的射线上。所有从网格边缘向外出发的射线按左上-右上-右下-左下-左上的顺序依次编号为 ,如下图:

对于每次询问,不同附加点所在的射线互不相同。每个附加点和最近的格点之间的线段也称为一条边,也有非负整数边权(注意,在角上的格点有可能和两个附加点同时相连)。

给定每个附加点的颜色(黑色或者白色),请你将网格内每个格点的颜色染成黑白二者之一,并使得所有两端颜色不同的边的边权和最小。请输出这个最小的边权和。

输入格式

第一行,三个正整数 ,分别表示水平、垂直直线的数量,以及询问次数。

接下来 行,每行 个非负整数。其中第 行的第 个非负整数 表示 间的边权。

接下来 行,每行 个非负整数。其中第 行的第 个非负整数 表示 间的边权。

接下来依次输入 组询问。第 组询问开头为一行一个正整数 表示这次询问附加点的总数。接下来 行每行三个非负整数。其中第 行依次为 表示第 个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色( 为白色, 为黑色)。

保证同一组询问内 互不相同。

每行的多个整数由空格分隔。

输出格式

输出 行,第 行输出一个非负整数,表示第 次询问染色之后两端颜色不同的边权和的最小值。

样例

输入样例 #1

2 3 1
9 4 7
3 8
10 5
2
19 3 1
17 9 0

输出样例 #1

12

输入样例 #2

见附件中的 traffic/traffic2.in

输出样例 #2

见附件中的 traffic/traffic2.ans

输入样例 #3

见附件中的 traffic/traffic3.in

输出样例 #3

见附件中的 traffic/traffic3.ans

输入样例 #4

见附件中的 traffic/traffic4.in

输出样例 #4

见附件中的 traffic/traffic4.ans

输入样例 #5

见附件中的 traffic/traffic5.in

输出样例 #5

见附件中的 traffic/traffic5.ans

数据范围与提示

【样例解释 #1】

最优方案: 为黑色; 为白色。

【数据范围】

测试点编号

对于所有数据,

保证对于每个 互不相同。