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

WA了很多次,不知道是什么问题,在这里发代码,路人请指教

Posted by pandm at 2009-08-31 11:32:48 on Problem 1847
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <climits>
#include <cctype>
#include <cassert>
#include <queue>
#define fillary(x,y,z) (fill_n(&(y),sizeof(x)/sizeof(y),(z)))
using namespace std;

//存储某个点的序号,以及到源点的当前最短路径
class VnD {
	public:
	int i, d;
	VnD(){}
	VnD(int ii, int dd) :i(ii), d(dd){}
	bool operator < (const VnD& a) const {
		return d > a.d;
	}
};

int N, A, B;
int g[200][200]; //图的临接矩阵
int d[200]; //某个点的最短路径的上界
bool sure[200]; //记录某个点的最短路径是否已经被确定
priority_queue<VnD> T; //临时点集合
const int BIGGEST = 9999999;

void input() {
	scanf("%d %d %d", &N, &A, &B);
	int i;
	fillary(g, g[0][0], BIGGEST);
	for (i = 1; i <= N; i++) {
		int j, k, id;
		scanf("%d", &j);
		for (k = 1; k <= j; k++) {
			scanf("%d", &id);
			if (k==1) {
				g[i][id] = 0;
			}
			else {
				g[i][id] = 1;
			}
		}
	}
}

int main() {

	input();
	fillary(sure, sure[0], false);

	fillary(d, d[0], BIGGEST);
	d[A] = 0;

	while(!T.empty())T.pop();

	int i;
	for (i = 1; i <= N; i++) {
		T.push( VnD(i, d[i]) );
	}

	int cur;
	int tmp;
	while (!T.empty() && !sure[B]) {
		cur = T.top().i;
		T.pop();
		if (sure[cur]) continue;
		sure[cur] = true;

		for (i = 1; i <= N; i++) {
			if (g[cur][i] == BIGGEST) continue;
			tmp = d[cur] + g[cur][i];
			if ( tmp < d[i]) {
				d[i]= tmp;
				T.push( VnD(i, d[i]) );
			}
		}
	}


	if (sure[B]) printf("%d\n", d[B]);
	else printf("-1\n");

	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