记录编号	411041	评测结果	AAAAAA
题目名称	[BJOI2006] 狼抓兔子	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.277 s
提交时间	2017-06-03 16:14:11	内存使用	78.81 MiB

# include <bits/stdc++.h>
# define INF 0x7fffffff
# define MAXN 2001000
using namespace std;

char buf[1 << 18], *fs, *ft;
inline char getc() { 
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int gn() { 
    int k = 0, f = 1;
    char c = getc();
    for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
    for(; isdigit(c); c = getc()) k = k * 10 + c - '0';
    return k * f;
}

struct edge { 
    int to, w;
    edge *ne;
    inline edge() { 
        to = 0, w = 0, ne = NULL;
    }
    inline edge(int to_, int w_, edge *ne_) { 
        to = to_;
        w = w_;
        ne = ne_;
    }
}*head[MAXN];

inline void addedge(int fr, int to, int w) { 
    head[fr] = new edge(to, w, head[fr]);
    head[to] = new edge(fr, w, head[to]);
}

int n, m, ans, S, T, dis[MAXN], q[MAXN << 3];
bool inq[MAXN];

void build(){
    S=0,T=((n-1)*(m-1))<<1|1;
    for (int i=1; i<=n; i++)
        for (int j=1; j<m; j++){
            int x=gn(),u,v;
            if (i==1) u=S,v=j;
            else if (i==n) u=((i-2)<<1|1)*(m-1)+j,v=T;
            else u=((i-2)<<1|1)*(m-1)+j,v=((i-1)<<1)*(m-1)+j;
            addedge(u, v, x);
        }
    for (int i=1; i<n; i++)
        for (int j=1; j<=m; j++){
            int x=gn(),u,v;
            if (j==1) u=((i-1)<<1|1)*(m-1)+1,v=T;
            else if (j==m) u=S,v=((i-1)<<1|1)*(m-1);
            else u=((i-1)<<1)*(m-1)+j-1,v=((i-1)<<1|1)*(m-1)+j;
            addedge(u, v, x);
        }
    for (int i=1; i<n; i++)
        for (int j=1; j<m; j++){
            int x=gn(),u,v;
            u=((i-1)<<1)*(m-1)+j,v=((i-1)<<1|1)*(m-1)+j;
            addedge(u, v, x);
        }
}

inline int spfa() { 
    int l = 1, r = 1;
    memset(dis, 42, sizeof(dis)); 
    dis[S] = 0;
    inq[S] = 1;
    q[1] = S;
    while(l <= r) { 
        int u = q[l++];
        inq[u] = 0;
        for(edge *e = head[u]; e; e = e->ne) { 
            if(dis[e->to] > dis[u] + e->w) { 
                dis[e->to] = dis[u] + e->w;
                if(!inq[e->to]) inq[e->to] = 1, q[++r] = e->to;
            }
        }
    }
    return dis[T];
}

inline void solve() { 
    if(n == 1 || m == 1) { 
        if(n > m) swap(n, m);
        ans = INF;
        for(int i = 1; i < m; i++) ans = min(gn(), ans);
        if(ans == INF) ans = 0;
        printf("%d\n", ans);
    } else { 
        build();
        printf("%d\n", spfa());
    }
}

int main() { 
# ifdef LOCAL
    freopen("in", "r", stdin);
# else 
    freopen("bjrabbit.in", "r", stdin);
    freopen("bjrabbit.out", "w", stdout);
# endif
    n = gn();
    m = gn();
    solve();
    return 0;
}