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

水题一道!dijkstra松弛技术无压力,注意%.3f和%.3lf!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Posted by MyTalent at 2013-04-21 11:20:34 on Problem 2253
#include <cstdio>
#include <cmath>
#define __max(a,b) ((a)>(b)?(a):(b))
#define __min(a,b) ((a)<(b)?(a):(b))
#define rep(i,repstt,repend) for(int i=repstt;i<repend;i++)
float x[222],y[222];
float dis(int a,int b){
	return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
int n;
bool vst[222];
float d[222];
void dijkstra(){
	rep(i,0,n){
		d[i]=10000000;
		vst[i]=0;
	}
	d[0]=0;
	rep(i,0,n){
		int mind=9999999,mink;
		rep(j,0,n)
		if(!vst[j]&&mind>d[j]){
			mind=d[j];
			mink=j;
		}
		vst[mink]=1;
		rep(j,0,n)d[j]=__min(d[j],__max(d[mink],dis(mink,j)));
	}
}
int main(){
	int cas=0;
	while(scanf("%d",&n)&&n){
		rep(i,0,n)scanf("%f%f",x+i,y+i);
		dijkstra();
		printf("Scenario #%d\nFrog Distance = %.3f\n\n",++cas,d[1]);//POJ 用%.f过
	}
	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