http://www.lydsy.com/JudgeOnline/problem.php?id=1001
#include <cstdio> #include <algorithm> #include <queue> #include <cmath> #include <cstring> #include <iostream> using namespace std; const int N = 2001000; #define inf 999999999 #define gc getchar() struct G{ int v, nxt, w; }G[N << 2]; int n, m, ans, num, S, T, head[N], dis[N]; bool vis[N]; queue <int> Q; inline int read(){ int x = 0, f = 1; char c = gc; while(c < '0' || c > '9') {if(c == '-') f = -1; c = gc;} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x * f; } void add(int u, int v, int w){ G[++num].v = v; G[num].w = w; G[num].nxt = head[u]; head[u] = num; } inline void spfa(){ for(int i = S; i <= T; i ++) dis[i] = inf, vis[i] = 0; dis[S] = 0; Q.push(S); while(!Q.empty()){ int topp = Q.front(); Q.pop(); vis[topp] = 0; for(int i = head[topp]; i; i = G[i].nxt){ int v = G[i].v; if(dis[v] > dis[topp] + G[i].w){ dis[v] = dis[topp] + G[i].w; if(!vis[v]) vis[v] = 1, Q.push(v); } } } ans = dis[T]; } inline 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 = read(), 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; add(u, v, x), add(v, u, x); } for(int i = 1; i < n; i ++) for(int j = 1; j <= m; j ++){ int x = read(), 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; add(u, v, x), add(v, u, x); } for(int i=1; i<n; i++) for(int j=1; j<m; j++){ int x = read(), u, v; u = ((i - 1) << 1) * (m - 1) + j, v = ((i - 1) << 1 | 1) * (m - 1) + j; add(u, v, x), add(v, u, x); } } int main() { n = read(), m = read(); build(); spfa(); printf("%d ",ans); return 0; }