马蜂清奇QAQ，常数爆大，求调。

Time limit exceeded on test 88

#include <cstdio>
#include <queue>
#include <cmath>

using i32 = int; using i64 = long long; // std::mt19937 rd(time(0));
constexpr i64 MAXN = 1e4 + 10, mod = 1e9 + 7, INF = 1e8, MAXM = 2e4 + 10; 

char buf[1 << 21], *p1 = buf, *p2 = buf, obuf[1 << 21], *O=obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline void read (i32 &sum) noexcept {
    i32 tf = 0; char ch = getchar(); sum = 0;
    while (ch < '0' || ch > '9') tf = ch == '-' ? 1 : 0, ch = getchar();
    while (ch >= '0' && ch <= '9') sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
    (tf) && (sum =- sum);
}template <typename i32, typename ...Args>
inline void read (i32 &tmp, Args &...tmps) noexcept{read(tmp); read(tmps...);}
void printt (i32 x) noexcept {if(x >= 10) printt(x / 10); putchar(x % 10 + '0');} 
inline void print (i32 x) noexcept{x < 0 ? putchar('-'), printt(-x) : printt(x);}
inline void put (i32 x) noexcept{print(x), putchar('\n');}

inline i32 lowbit(i32 x) noexcept{
	return x & -x;
}

struct edge{i32 v, d, nex;}g[MAXM], E[MAXM][(1 << 10) + 5];

i32 mark, S, T, cnt = 1, first[MAXN], dep[MAXN], cur[MAXN], L[MAXN], l[MAXN], I[MAXN], U[MAXN];
i32 n, m, k, dp[MAXN], _g[MAXN], t, id[MAXN];
std::queue<i32>q;

inline void update(i32 u, i32 v, i32 d) noexcept{
	g[++cnt] = (edge){v, d, first[u]}, first[u] = cnt;
}

inline i32 bfs() noexcept{
	for (i32 i = 1; i <= T; i++)
		dep[i] = 0;
	
	while (!q.empty())
		q.pop();
	q.push(S), dep[S] = 1;
	
	while (!q.empty()){
		i32 nex = q.front(); q.pop();
		
		for (i32 i = first[nex]; i; i = g[i].nex){
			if (g[i].d > 0 && !dep[g[i].v]){
				dep[g[i].v] = dep[nex] + 1, q.push(g[i].v);
				
				if (g[i].v == T)
					return 1;
			}
		}
	}
	
	return 0;
}

i32 dfs(i32 u, i32 flow) noexcept{
	if (u == T)
		return flow;
	i32 res = flow;
	
	for (i32 i = cur[u]; i && flow; i = g[i].nex){
		cur[u] = i;
		
		if (g[i].d > 0 && dep[g[i].v] == dep[u] + 1){
			i32 k = dfs(g[i].v, std::min(flow, g[i].d));
			if (!k)
				dep[g[i].v] = 0;
			g[i].d -= k, g[i ^ 1].d += k, flow -= k;
		}
	}
	
	return res - flow;
}

inline i32 Dinic() noexcept{
	i32 maxflow = 0;
	while (bfs()){
		for (i32 i = 1; i <= T; i++)
			cur[i] = first[i];
			
		maxflow += dfs(S, INF);
	}
	
	return maxflow;
}

inline i64 Bfs() noexcept{
	for (i32 i = 1; i <= T; i++) dep[i] = 0;

	while (!q.empty())
		q.pop();
	q.push(S), dep[S] = 1;
	
	while (!q.empty()){
		i32 nex = q.front(); q.pop();
		
		for (i32 i = first[nex]; i; i = g[i].nex){
			if (g[i].d > 0 && !dep[g[i].v]){
				dep[g[i].v] = dep[nex] + 1, q.push(g[i].v);
				U[g[i].v] = nex, I[g[i].v] = i;
			}
			if (dep[T])
				break;
		}
		
		if (dep[T])
			break;
	}
	
	if (!dep[T]) return 0;

	i64 ans = 25, u = T;
	while (u != S)
		ans = std::min(ans, (i64)g[I[u]].d), u = U[u];
	u = T;
	while (u != S)
		g[I[u]].d -= ans, g[I[u] ^ 1].d += ans, u = U[u];
	
	return ans;	
}

inline i64 FF() noexcept{
	i64 maxflow = 0, x;
	while (x = Bfs())
		maxflow += x;
	return maxflow;
}

int main() noexcept{
	read(n, m, k, t);

	mark = (1ll << k) - 1, S = 1, T = n;
	
	for (i32 i = 1, x, y, z; i <= m; i++){
		read(x, y, z);
		update(x, y, z), update(y, x, 0);
	}
	
	dp[0] = Dinic();
	
	for (i32 i = 2; i < cnt; i++)
		E[i][0] = g[i];
	
	L[1] = 1;
	for (i32 i = 2; i <= mark; i++)
		L[i] = L[i >> 1] + 1;
	
	for (i32 i = 1; i <= mark; i++){
		l[i] = lowbit(i);
		for (i32 j = 2; j < cnt; j++)
			g[j] = E[j][i ^ l[i]];
		
		g[L[l[i]] << 1].d = 25;
		dp[i] = FF() + dp[i ^ l[i]];
	
		for (i32 j = 2; j < cnt; j++)
			E[j][i] = g[j];
	}

	while (t--){
		for (i32 i = 1; i <= k; i++)
			read(id[i]);
		
		i32 ans = INF;
		for (i32 i = 1; i <= mark; i++)
			_g[i] = _g[i ^ l[i]] + id[L[l[i]]];
		for (i32 i = 0; i <= mark; i++)
			ans = std::min(ans, dp[i] + _g[i ^ mark]);
		
		put(ans);
	}
    return 0;
}