8
31
2015
4

BZOJ1001[BeiJing2006]狼抓兔子

写的时候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;
}
Category: BZOJ | Tags: 最短路 SPFA | Read Count: 818
Avatar_small
Flandre Scarlet 说:
2015年9月04日 00:20

%%%居然是SPFA
格点图不是Dijk更快吗

Avatar_small
ctu student login 说:
2022年8月19日 07:26 Online students will find M.U.S.E. housed under student portals. Log in to your student portal now! Online · Denver South · ctu student login Colorado Springs. Join one of CTU 2021. CTU Mobile by Colorado Technical University™ is a 2016 International E-Learning Award (IELA) winner for mobile learning: academic division. ctu student login portal
Avatar_small
Meghalaya Board 7th 说:
2022年8月24日 23:34

Meghalaya Board Model Paper 2023 Class 7 Pdf Download with Answers for Bengali Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Meghalaya Board 7th Class Model Paper Questions to Term1 & Term2 Exams at official website. New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com