记录编号	37787	评测结果	AAAAAAAAAA
题目名称	栅格网络流	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.126 s
提交时间	2012-04-08 12:23:44	内存使用	0.65 MiB

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int N = 100*100+20, INF = 0x7fffffff;
int T, n, m, e, a, b, s, t;
int f[N], l[N], p[N], o[110][110];
vector <int> G[N], c[N];
void adde(int u, int v, int w) {
    G[u].push_back(v); c[u].push_back(w);
    G[v].push_back(u); c[v].push_back(w);
}
priority_queue<pair<int, int> > q;
int Dijkstra() {
    memset(l, 0, sizeof(l));
    for(int i=s; i<=t; i++) f[i] = INF;
    f[s] = 0;
    q.push(make_pair(-f[s], s));
    while(!q.empty()) {
        int x = q.top().second; q.pop();
        if(l[x]) continue;
        l[x] = 1;
        for(int i=0; i<G[x].size(); i++) {
            int v = G[x][i];
            if(f[v] > f[x] + c[x][i]) {
                f[v] = f[x] + c[x][i];
                q.push(make_pair(-f[v], v));
            }
        }
    }
    return f[t];
}
int main() {
    freopen("flowa.in", "r", stdin);
    freopen("flowa.out", "w", stdout);
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &m);
        n--, m--;
        for(int i=0; i<N; i++)
            G[i].clear(), c[i].clear();
        s = o[0][0] = 0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                o[i][j] = ++o[0][0];
        t = o[0][0]+1;
        for(int j=1; j<=m; j++) {
            scanf("%d", &e);
            adde(s, o[1][j], e);
        }
        for(int i=1; i<n; i++)
            for(int j=1; j<=m; j++) {
                scanf("%d", &e);
                adde(o[i][j], o[i+1][j], e);
            }
        for(int i=1; i<=m; i++) {
            scanf("%d", &e);
            adde(t, o[n][i], e);
        }
        for(int i=1; i<=n; i++) {
            scanf("%d", &e);
            adde(t, o[i][1], e);
            for(int j=1; j<m; j++) {
                scanf("%d", &e);
                adde(o[i][j], o[i][j+1], e);
            }
            scanf("%d", &e);
            adde(s, o[i][m], e);
        }
        e = Dijkstra();
        printf("%d\n", e);
    }
    return 0;
}