记录编号	37790	评测结果	AAAAAT
题目名称	[BJOI2006] 狼抓兔子	最终得分	83
用户昵称	王者自由	是否通过	未通过
代码语言	C++	运行时间	2.076 s
提交时间	2012-04-08 15:06:24	内存使用	37.76 MiB

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int N = 710, INF = 0x7fffffff;
const int NN = N * N * 2 + 10;
int n, m, s, t, e;
int f[NN], l[NN], o[N][N][2];
vector<int> G[NN], c[NN];
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 u = q.top().second; q.pop();
        if(!l[u]) {
            l[u] = 1;
            for(int i=0; i<G[u].size(); i++) {
                int v = G[u][i];
                if(!l[v] && f[v] > f[u] + c[u][i]) {
                    f[v] = f[u] + c[u][i];
                    q.push(make_pair(-f[v], v));
                }
            }
        }
    }
    return f[t];
}
int main() {
    freopen("bjrabbit.in", "r", stdin);
    freopen("bjrabbit.out", "w", stdout);
    scanf("%d %d", &n, &m);
    n--, m--;
    s = o[0][0][0] = 0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            for(int k=0; k<2; k++)
                o[i][j][k] = ++o[0][0][0];
    t = o[0][0][0] + 1;
    for(int i=1; i<=m; i++) {
        scanf("%d", &e);
        adde(s, o[1][i][0], e);
    }
    for(int i=1; i<n; i++)
        for(int j=1; j<=m; j++) {
            scanf("%d", &e);
            adde(o[i][j][1], o[i+1][j][0], e);
        }
    for(int i=1; i<=m; i++) {
        scanf("%d", &e);
        adde(t, o[n][i][1], e);
    }
    for(int i=1; i<=n; i++) {
        scanf("%d", &e);
        adde(t, o[i][1][1], e);
        for(int j=1; j<m; j++) {
            scanf("%d", &e);
            adde(o[i][j][0], o[i][j+1][1], e);
        }
        scanf("%d", &e);
        adde(s, o[i][m][0], e);
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            scanf("%d", &e);
            adde(o[i][j][0], o[i][j][1], e);
        }
    printf("%d\n", Dijkstra());
    return 0;
}