BZOJ1001 - [BeiJing2006]狼抓兔子

2017/03/22

我好菜啊 _(:з」∠)_

一道经典模板题!

代码

数组开够!

  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]);
}