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

这个题不就是dij的变形吗?高人帮我看下代码错在哪里?

Posted by 547880119 at 2009-09-16 16:19:49 on Problem 2253
#include <iostream>
#include <queue>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;

int N;

struct NODE{
	int x;int y;
}node[201];

double longest[201];
bool vis[201];

double d[201][201];

inline double dis(int a,int b)
{
	return sqrt(1.0*(node[a].x-node[b].x)*(node[a].x-node[b].x)+
		1.0*(node[a].y-node[b].y)*(node[a].y-node[b].y));
}

struct cmp
{
	bool operator () (const int &a,const int &b)
	{
		return longest[a]>longest[b];
	}
};

double djs()
{
	priority_queue<int,vector<int>,cmp> pq;
	

	longest[1] = 0.0;
	pq.push(1);

	while(!pq.empty())
	{
		int x = pq.top();
		pq.pop();
	//	cout << "vis" <<x << endl;
		vis[x] = 1;
		if(x==2) return longest[2];

		for(int i = 1; i <= N; i++)
		{
			if(vis[i]) continue;
			if(longest[i]>(longest[x]>d[i][x]?longest[x]:d[i][x]))
			{
				longest[i] = longest[x]>d[i][x]?longest[x]:d[i][x];
				pq.push(i);
			}
		}
	}

	return -1;
}

int main()
{
	int t=1;
	while(scanf("%d",&N)&&N!=0)
	{
		memset(node,0,sizeof(node));
		memset(d,0,sizeof(d));
		memset(vis,0,sizeof(vis));
		for(int i = 1; i <= N; i++)
			longest[i] = 10000000.0;

		for(int i = 1; i <= N; i++)
		{
			scanf("%d %d",&node[i].x,&node[i].y);
			for(int j = 1; j <= i; j++){
				d[i][j] = d[j][i] = dis(i,j);
			}
		}

		cout << "Scenario #" << t <<endl
			<< "Frog Distance = " << setiosflags(ios::fixed) << setprecision(3) << djs() << endl << endl;
		t++;
	}
	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