减舟's Blog

写的时候RE了，然后调了下，发现要在SPFA里改成滚动数组，不然边数比较多会溢出。

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
struct node {
	int t, v;   
};
const int M = 2000001;
int n, m, pn, a[1001][1001][2], D[2000001], f[2000001];
bool b[2000001];
vector <node> G[2000001];
     
void add(int a, int b, int c) {
	node t1 = {b, c}, t2 = {a, c};
	G[a].push_back(t1), G[b].push_back(t2);
}

void init() {
	scanf("%d%d", &n, &m);
	pn = 2;
	for (int i = 1; i < n; i++)
    	for (int j = 1; j < m; j++)
        	for (int k = 0; k <= 1; k++)
            	a[i][j][k] = ++pn;
	for (int i = 1; i <= pn; i++) G[i].clear();
	
	for (int i = 1; i < n; i++) a[i][0][1] = 1;
	for (int i = 1; i < m; i++) a[n][i][1] = 1;
	for (int i = 1; i < n; i++) a[i][m][0] = 2;
	for (int i = 1; i < m; i++) a[0][i][0] = 2;
    
	int tmp;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < m; j++)
			scanf("%d", &tmp), add(a[i - 1][j][0], a[i][j][1], tmp);
	for (int i = 1; i < n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d", &tmp), add(a[i][j - 1][1], a[i][j][0], tmp);
	for (int i = 1; i < n; i++)
		for (int j = 1; j < m; j++)
			scanf("%d", &tmp), add(a[i][j][0], a[i][j][1], tmp);
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	
	init();
	
	int head = 0, tail = 1;
	memset(b, 0, sizeof(b));
	memset(D, 0x3f, sizeof(D));
	D[1] = 0; b[1] = 1; f[1] = 1;
	while (head < tail) {
    	int tmp = f[++head]; b[tmp] = 0;
    	if (head == M) head = 0;
		for (int i = 0; i < G[tmp].size(); i++)
			if (D[G[tmp][i].t] > D[tmp] + G[tmp][i].v) {
				D[G[tmp][i].t] = D[tmp] + G[tmp][i].v;
				if (!b[G[tmp][i].t]) {
					b[G[tmp][i].t] = 1, f[++tail] = G[tmp][i].t;
					if (tail == M) tail = 0;
				}
			}
	}
	printf("%d\n", D[2]);
	return 0;
}