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也可以变种呀~附0msdij代码

Posted by DMChusen at 2012-07-06 19:19:07 on Problem 2253
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
#define inf 0x7fffffff
int x[210],y[210],n,mark[210];
double map[210][210],v[210];
double getit(int i,int j)
{
	int d;
	double f;
	d=(y[i]-y[j])*(y[i]-y[j])+(x[i]-x[j])*(x[i]-x[j]);
	f=sqrt(d);
	return f;
}
double max(double a,double b)
{
	if(a>=b)
		return a;
	else
		return b;
}
double dijkstra()
{
	memset(mark,0,sizeof(mark));
	int i,j,k;
	double t,ans=0;
	for(i=0;i<n;i++)
	{
		v[i]=map[0][i];
	}
	v[i]=0;
	mark[0]=1;
	for(i=1;i<n;i++)
	{
		t=inf;	//t=v[i];
		for(j=0;j<n;j++)
		{
			if(!mark[j]&&v[j]<t)
			{
				t=v[j];
				k=j;	
			}
		}
		mark[k]=1;

		for(j=0;j<n;j++)
		{
			double temp=max(map[k][j],v[k]);
			if(temp<v[j])
				v[j]=temp;
		}
	}
	ans=v[1];
	return ans;
}
int main()
{
	int i,j,k,test=0;
	double weight,ans;
	while(scanf("%d",&n)==1)
	{	
		test++;
		memset(map,0,sizeof(map));
		if(n==0)
			break;
		for(i=0;i<n;i++)
		{	
			for(j=0;j<n;j++)
				map[i][j]=inf;
			map[i][i]=0;
		}		
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&x[i],&y[i]);			
			for(j=0;j<i;j++)
			{
				weight=getit(i,j);
				map[i][j]=weight;
				map[j][i]=weight;
			}			
		}				
		ans=dijkstra();
		printf("Scenario #%d\n",test);
		printf("Frog Distance = %.3f\n\n",ans);
	}
	
	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