BZOJ1001 - [BeiJing2006]狼抓兔子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_N = 1100;
const int ESIZ = (MAX_N * MAX_N) * 6 + 1E5;
#define hash(x, y, t) ((((x) * MAX_N + (y)) << 1) | (t) )
const int Snode = hash(0, 0, 0);
const int Tnode = hash(MAX_N - 20, 0, 0);

struct tgno {
    int v, w; tgno* n;
} POOL[ESIZ]; int ppos;
tgno *Head[ESIZ];

void _add(int u, int v, int w) {
    POOL[ppos].v = v; POOL[ppos].w = w;
    POOL[ppos].n = Head[u]; Head[u] = &POOL[ppos++];
}

void addEdge(int u, int v, int w) {
    _add(u, v, w), _add(v, u, w);
}

int N, M;

typedef pair<int, int> PII;
int dis[ESIZ];
priority_queue<PII, vector<PII>, greater<PII> > Q;
void Dijkstra(int S, int T) {
    memset(dis, 0x3f, sizeof(dis));
    Q.push(PII(0, S)); dis[S] = 0;
    while(!Q.empty()) {
        int cur = Q.top().second;
        if(dis[cur] < Q.top().first) { Q.pop(); continue; }
        Q.pop();
        if(cur == T) return;
        typedef tgno* It;
        for(It i=Head[cur];i;i=i->n) {
            if(dis[i->v] > dis[cur] + i->w) {
                dis[i->v] = dis[cur] + i->w;
                Q.push(PII(dis[i->v], i->v));
            }
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);

    if(N == 1 || M == 1) {
        int ans = 0x3f3f3f3f, t = 0;
        while(scanf("%d", &t) != EOF) ans = min(ans, t);
        printf("%d\n", ans); return 0;
    }

    int w;

    // 横边
    for(int j=1;j<M;j++) {
        scanf("%d", &w);
        addEdge(Snode, hash(1, j, 0), w); // S 到第一行上三角
    }

    for(int i=2;i<N;i++) {
        for(int j=1;j<M;j++) {
            scanf("%d", &w);
            addEdge(hash(i-1, j, 1), hash(i, j, 0), w); // 上一行下三角到当前上三角
        }
    }

    for(int j=1;j<M;j++) {
        scanf("%d", &w);
        addEdge(hash(N-1, j, 1), Tnode, w); // 最后一行下三角到 T
    }

    // 纵边
    for(int i=1;i<N;i++) {
        scanf("%d", &w); addEdge(Tnode, hash(i, 1, 1), w); // T 到 第一列下三角
        for(int j=2;j<M;j++) {
            scanf("%d", &w);
            addEdge(hash(i, j-1, 0), hash(i, j, 1), w); // 上一列上三角到当前下三角
        }
        scanf("%d", &w); addEdge(hash(i, M-1, 0), Snode, w); // 最后一列上三角到 S
    }

    // 斜边
    for(int i=1;i<N;i++) {
        for(int j=1;j<M;j++) {
            scanf("%d", &w);
            addEdge(hash(i, j, 0), hash(i, j, 1), w); // 同方块内斜边
        }
    }

    Dijkstra(Snode, Tnode);

    printf("%d\n", dis[Tnode]);
}