BZOJ1001: [BeiJing2006]狼抓兔子

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 using namespace std;
 5 struct node {
 6     int t, v;   
 7 };
 8 const int M = 2000001;
 9 int n, m, pn, a[1001][1001][2], D[2000001], f[2000001];
10 bool b[2000001];
11 vector <node> G[2000001];
12       
13 void add(int a, int b, int c) {
14     node t1 = {b, c}, t2 = {a, c};
15     G[a].push_back(t1), G[b].push_back(t2);
16 }
17  
18 void init() {
19     scanf("%d%d", &n, &m);
20     pn = 2;
21     for (int i = 1; i < n; i++)
22         for (int j = 1; j < m; j++)
23             for (int k = 0; k <= 1; k++)
24                 a[i][j][k] = ++pn;
25     for (int i = 1; i <= pn; i++) G[i].clear();
26      
27     for (int i = 1; i < n; i++) a[i][0][1] = 1;
28     for (int i = 1; i < m; i++) a[n][i][1] = 1;
29     for (int i = 1; i < n; i++) a[i][m][0] = 2;
30     for (int i = 1; i < m; i++) a[0][i][0] = 2;
31      
32     int tmp;
33     for (int i = 1; i <= n; i++)
34         for (int j = 1; j < m; j++)
35             scanf("%d", &tmp), add(a[i - 1][j][0], a[i][j][1], tmp);
36     for (int i = 1; i < n; i++)
37         for (int j = 1; j <= m; j++)
38             scanf("%d", &tmp), add(a[i][j - 1][1], a[i][j][0], tmp);
39     for (int i = 1; i < n; i++)
40         for (int j = 1; j < m; j++)
41             scanf("%d", &tmp), add(a[i][j][0], a[i][j][1], tmp);
42 }
43  
44 int main() {
45     //freopen("input.txt", "r", stdin);
46     //freopen("output.txt", "w", stdout);
47      
48     init();
49      
50     int head = 0, tail = 1;
51     memset(b, 0, sizeof(b));
52     memset(D, 0x3f, sizeof(D));
53     D[1] = 0; b[1] = 1; f[1] = 1;
54     while (head < tail) {
55         int tmp = f[++head]; b[tmp] = 0;
56         if (head == M) head = 0;
57         for (int i = 0; i < G[tmp].size(); i++)
58             if (D[G[tmp][i].t] > D[tmp] + G[tmp][i].v) {
59                 D[G[tmp][i].t] = D[tmp] + G[tmp][i].v;
60                 if (!b[G[tmp][i].t]) {
61                     b[G[tmp][i].t] = 1, f[++tail] = G[tmp][i].t;
62                     if (tail == M) tail = 0;
63                 }
64             }
65     }
66     printf("%d\n", D[2]);
67     return 0;
68 }