Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

SPFA,WA我N次,终于过了,INF要设置大点,也不能太大

Posted by td1425141034 at 2016-07-23 17:45:09 on Problem 2049
//SPFA求网格最短路问题
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 201;
#define INF MAXN*MAXN     
int W[MAXN][MAXN], H[MAXN][MAXN];
int dis[MAXN][MAXN];
int maxX, maxY;
struct Point{
	int x, y;
	Point(int x = 0, int y = 0){ this->x = x; this->y = y; }
};
bool isLeg(int x, int y){
	return x > -1 && y > -1 && x <=maxX&&y <=maxY;
}
void SPFA(){          //SPFA
	queue<Point>Q;
	Point next, now;
	Q.push(Point(0,0));
	for (int i = 0; i < MAXN;i++)
	for (int j = 0; j < MAXN; j++)
		dis[i][j] = INF;
	dis[0][0] = 0;
	while (!Q.empty()){
		now = Q.front();
		Q.pop();
		int x = now.x,y = now.y;
		/*接下来进行松弛操作*/

		//检查左边网格
		if (isLeg(x - 1, y) && dis[x - 1][y] > dis[x][y] + W[x][y]){
			dis[x - 1][y] = dis[x][y] + W[x][y];
			Q.push(Point(x-1,y));    //入队
		}
		//检查右边网格
		if (isLeg(x+1, y) && dis[x+1][y] > dis[x][y] + W[x+1][y]){
			dis[x +1][y] = dis[x][y] + W[x+1][y];
			Q.push(Point(x +1, y));    //入队
		}
		//检查上方网格
		if (isLeg(x, y+1) && dis[x][y+1] > dis[x][y] + H[x][y+1]){
			dis[x][y+1] = dis[x][y] + H[x][y+1];
			Q.push(Point(x, y+1));    //入队
		}
		//检查下方网格
		if (isLeg(x, y-1) && dis[x][y-1] > dis[x][y] + H[x][y]){
			dis[x][y-1] = dis[x][y] + H[x][y];
			Q.push(Point(x, y-1));    //入队
		}
	}
}
int main(){
	int m, n, i, j,x,y,d,t;
	while (scanf("%d%d", &n, &m) && n != -1){
		memset(W, 0, sizeof(W));
		memset(H, 0, sizeof(H));
		maxX = maxY = 0;
		for (i = 0; i < n; i++){
			scanf("%d%d%d%d", &x, &y, &d, &t);
			if (d){   //y轴平行
				maxX = max(x, maxX);
				maxY = max(y+t, maxY);
				for (j = 0; j < t; j++)
					W[x][y + j] =INF;      //设置为无穷
			}
			else{
				maxX = max(x+t, maxX);
				maxY = max(y, maxY);
				for (j = 0; j < t; j++)
					H[x + j][y] =INF;
			}
		}
		for (i = 0; i < m; i++){
			scanf("%d%d%d", &x, &y, &d);
			if (d)
				W[x][y] = 1;
			else
				H[x][y] = 1;
		}
		double fx, fy;
		cin >> fx >>fy;//scanf("%lf%lf", &fx, &fy);    //Nemo的位置
		x = int(fx), y = int(fy);
		if (x > maxX || y > maxY)  //在迷宫外面
			printf("0\n");
		else{
			SPFA();
			if (dis[x][y]>=INF)
				printf("-1\n");
			else 
				printf("%d\n", dis[x][y]);
		}
		
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator