2786. T4-[CSP-S 2021] 交通规划traffic
时间限制：5000 MS 内存限制：512 MB
题目描述
## 题目描述 给定一个平面上 $n$ 条水平直线和 $m$ 条垂直直线，它们相交形成 $n$ 行 $m$列的网格，从上到下第 $r$ 条水平直线和从左到右第$ c$条垂直直线之间的交点称为格点 $(r,c)$。 网格中任意两个水平或垂直相邻的格点之间的线段称为一条边，每条边有一个非负整数边权。 进行 $T$ 次询问，每次询问形式如下： 给出 $k（T$次询问的$ k$ 可能不同）个附加点，每个附加点位于一条从网格边缘向外出发的射线上。 所有从网格边缘向外出发的射线按左上-右上-右下-左下-左上的顺序依次编号为 $1$到 $2n+2m$，如下图：  对于每次询问，不同附加点所在的射线互不相同。 每个附加点和最近的格点之间的线段也称为一条边，也有非负整数边权（注意，在角上的格点有可能和两个附加点同时相连）。 给定每个附加点的颜色（黑色或者白色），请你将网格内每个格点的颜色染成黑白二者之一，并使得所有两端颜色不同的边的边权和最小。 请输出这个最小的边权和。 ## 输入格式 第一行 $3$ 个正整数$ n,m,T$分别表示水平、垂直直线的数量，以及询问次数。 接下来 $n-1$ 行，每行 $m$ 个非负整数。其中第$ i$行的第 $j$个非负整数$ x1i,j$ 表示 $(i,j)$和 $(i+1,j)$ 间的边权。 接下来 $n$行，每行$ m-1$ 个非负整数。其中第 $i$ 行的第$ j$个非负整数$ x2i,j$表示$ (i,j)$和$ (i,j+1)$ 间的边权。 接下来依次输入$ T$组询问。 第$ i$ 组询问开头为一行一个正整数$ ki$表示这次询问附加点的总数。 接下来$ ki$行每行三个非负整数。其中第 $j$行依次为 $x3i,j,pi,j,ti,j$ 表示第 $i$个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色（$0$为白色，$1$为黑色）。保证同一组询问内$ pi,j$互不相同。 每行的多个整数由空格分隔。 ## 输出格式 输出$ T$行，第$ i$ 行输出一个非负整数，表示第$ i$次询问染色之后两端颜色不同的边权和的最小值。 ## 数据范围  对于所有数据，$2\len,m\le500,1\leT\le50,1\leki\lemin{2(n+m),50},1\le\sumi=1Tki\le50,0\lex\le106,1\lep\le2(n+m),t\in{0,1}$。 保证对于每个$ i\in[1,T]，pi,j$互不相同。 ```in4 2 3 1 9 4 7 3 8 10 5 2 19 3 1 17 9 0 ``` ```out4 12 ``` ## 说明 最优方案：$(1,3),(1,2),(2,3)$为黑色；$(1,1),(2,1),(2,2)$ 为白色。