45pts 只能过 k<=3 求救

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, T, k;
int row[505][505], col[505][505], sta[250505], blo[250505], val[250505], bvl[250505], cnt;
int dis[28][250505], g[55][55], f[55][55];
bool vis[250055];
vector< pair<int, int> > G[505 * 505 + 50];
priority_queue< pair<int, int> > Q;
struct ex_node{//扩展：在边缘的节点 
	public:
		int d, p, c;
		friend istream & operator >> (istream &is, ex_node &qaq){
			is >> qaq.d >> qaq.p >> qaq.c;
			return is;
		}
};
vector<ex_node> ext;
int gid(int x, int y){//坐标转下标 
	return (x - 1) * (m - 1) + y;
}
void add(int u, int v, int c){//加边 
//	cerr << ">" << u << " " << v << " " << c << "\n";
	G[u].emplace_back(make_pair(v, c));
	G[v].emplace_back(make_pair(u, c));
}
void add(int x, int y, int xx, int yy, int c){//格点加边 
	int u = gid(x, y), v = gid(xx, yy);
	add(u, v, c);
}
void clr(){//多测清空 
	cnt = (n - 1) * (m - 1);
	memset(sta, -1, sizeof sta);
	memset(dis, 0x3f, sizeof dis);
	memset(f, 0x3f, sizeof f);
	memset(blo, 0, sizeof blo);
	memset(g, 0x3f, sizeof g);
	memset(val, 0, sizeof val);
	memset(bvl, 0, sizeof bvl);
	for (int i = 1; i <= n * m; i++)
		G[i].clear();
}
void dijkstra(int s){//跑最短路 
	memset(vis, 0, sizeof vis);
	int p = (s - (n - 1) * (m - 1) + 1) / 2;
	dis[p][s] = 0;
	Q.push({0, s});
	while (!Q.empty()){
		int u = Q.top().second;
	//	cerr << ":" << s << " " << p << " " << u << " " << dis[p][u] << "\n";
		Q.pop();
		if (vis[u])
			continue;
		vis[u] = 1;
		for (auto tmp : G[u]){
			int v = tmp.first, c = tmp.second;
			if (dis[p][v] > dis[p][u] + c){
				dis[p][v] = dis[p][u] + c;
				Q.push({-dis[p][v], v});
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> T;
	for (int i = 1; i < n; i++)
		for (int j = 1; j <= m; j++)
			cin >> col[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < m; j++)
			cin >> row[i][j];
	while (T--){
		cin >> k;
		clr();
		bool ovo = 1, owo = 0;
		for (int i = 1; i <= k; i++){
			ex_node awa;
			cin >> awa;
			ext.emplace_back(awa);
			ovo &= awa.c;
			owo |= awa.c;
			sta[awa.p] = awa.c;
			val[awa.p] = awa.d;
		}
		if (ovo == owo){//所有附加点同色 
			cout << "0\n";
			continue;
		}
		for (int i = 1; i < n - 1; i++)
			for (int j = 1; j < m; j++)
				add(i, j, i + 1, j, row[i + 1][j]);
		for (int i = 1; i < n; i++)
			for (int j = 1; j < m - 1; j++)
				add(i, j, i, j + 1, col[i][j + 1]);//建网格内部在对偶图上对应的边 
		int lst = -1;
		for (int i = 1; i <= (n + m << 1); i++){//找外圈的块 
			if (sta[i] == -1)
				blo[i] = cnt;
			else if (lst = -1 || sta[i] ^ lst == 1){
				blo[i] = ++cnt;
				lst = sta[i];
				bvl[cnt] = val[i];
			}else
				blo[i] = cnt;
		}
		for (int i = 1; i <= (n + m << 1); i++){//找外圈的块 
			if (sta[i] == -1)
				blo[i] = cnt;
			else
				break;
		}
	//	cerr << cnt << "\n";
		for (int i = (n - 1) * (m - 1) + 1; i < cnt; i++)
			add(i, i + 1, bvl[i]);
		add(cnt, (n - 1) * (m - 1) + 1, bvl[cnt]);
	//	cerr << "qwq\n";
		for (int i = 1; i < m; i++)//边缘的点建边 
			add(blo[i], gid(1, i), row[1][i]);
		for (int i = m + 1; i < m + n; i++)
			add(blo[i], gid(i - m, m - 1), col[i - m][m]);
	//	cerr << "qwq\n";
		for (int i = m + n + 1;  i < (m << 1) + n; i++)
			add(blo[i], gid(n - 1, m - (i - m - n)), row[n][m - (i - m - n)]);
		for (int i = (m << 1) + n + 1; i < (m + n << 1); i++)
			add(blo[i], gid(n - (i - (m << 1) - n), 1), col[n - (i - (m << 1) - n)][1]);
		for (int i = (n - 1) * (m - 1) + 1; i <= cnt; i += 2)
			dijkstra(i);
		for (int i = (n - 1) * (m - 1) + 1; i <= cnt; i += 2)//取出每一块的最短路 
			for (int j = (n - 1) * (m - 1) + 1; j <= cnt; j++){
				int p = (i - (n - 1) * (m - 1) + 1) / 2;
			//	cerr << i << " " << j << " " << " " << p << "\n";
				g[i - (n - 1) * (m - 1)][j - (n - 1) * (m - 1)] = dis[p][j];
				g[j - (n - 1) * (m - 1)][i - (n - 1) * (m - 1)] = dis[p][j];
			}
		int ccnt = cnt - (n - 1) * (m - 1);
		for (int len = 1; len <= ccnt; len++){//区间 dp 合并 
			for (int i = 1; i + len - 1 <= ccnt; i++){
				int j = i + len - 1;
			//	cerr << i << " " << j << " "; 
				if (len == 1)
					f[i][j] = 0;
				else if (len == 2)
					f[i][j] = g[i][j];
				for (int k = i + 1; k < j; k++)
					f[i][j] = min(f[i][j], f[i][k - 1] + g[i][k] + f[k + 1][j]);
			//	cerr << g[i][j] << "\n";
			}
		}
		cout << f[1][ccnt] << "\n";
	}
	return 0;
}