2677.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 52 行

Problem Id:2677  User Id:fzk 
#include <stdio.h>
#include <memory.h>
#include <math.h>
struct point
{
	double x, y;
};
double dis( point &a, point &b )
{
	return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
double s[1010][1010];
point p[1010];
int main( )
{
	int n, i, j;
	double t, ans;
	while( scanf( "%d", &n ) == 1 )
	{
	
		for( i=1; i<=n; i++ )
			scanf( "%lf %lf", &p[i].x, &p[i].y );
		p[0].x = p[1].x;
		p[0].y = p[1].y;
		n++;
		for( i=0; i<n; i++ )
		for( j=i+1; j<n; j++ )
			s[i][j] = -1;
		s[0][1] = 0;
		for( i=0; i<n-1; i++ )
		for( j=i+1; j<n-1; j++ )
		{
			t = s[i][j] + dis( p[i], p[j+1] );
			if( s[j][j+1] == -1 || t < s[j][j+1] )
				s[j][j+1] = t;

			t = s[i][j] + dis( p[j], p[j+1] );
			if( s[i][j+1] == -1 || t < s[i][j+1] )
				s[i][j+1] = t;
		}
		ans = 1e100;
		for( i=0; i<n-1; i++ )
			if( ans > ( t = s[i][n-1] + dis( p[i], p[n-1] ) ) )
				ans = t;
		printf( "%.2lf\n", ans );
	}
	return 0;
}