pku2502.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <math.h>
#define SLOW (10000.0 / 60.0)
#define FAST (40000.0 / 60.0)

double dis[205][205];
double mindis[205];
int use[205];

typedef struct 
{
	int x, y, lable;
} Point;

Point p[200];

double calcdis(int i, int j)
{
	return sqrt(1.0 * (p[i].x - p[j].x) * (p[i].x - p[j].x) + 1.0 * (p[i].y - p[j].y) * (p[i].y - p[j].y));
}

void DIJ(int k)
{
	int i, j, u;
	double min;
	
	for (i = 1; i < k; i++)
	{
		mindis[i] = dis[i][0];
		use[i] = 0;
	}
	
	use[0] = 1;

	for (j = 1; j < k; j++)
	{
		min = 1e30;
		u = 0;

		for (i = 0; i < k; i++)
		{
			if (use[i] == 0 && mindis[i] < min)
			{
				min = mindis[i];
				u = i;
			}
		}
		use[u] = 1;

		for (i = 1; i < k; i++)
		{
			if (!use[i] && mindis[i] > min + dis[i][u])
			{
				mindis[i] = min + dis[i][u];
			}
		}
	}
	printf("%.0lf\n", mindis[1]);
}

int main()
{
	int x, y;
	int i, j, k;
	double tmpdis;
	int lable;
	k = 2;

	scanf("%d %d %d %d", &p[0].x, &p[0].y, &p[1].x, &p[1].y);
	p[0].lable = 0;
	p[1].lable = 1;
	lable = 2;
	while (scanf("%d%d", &x, &y) != -1)
	{
		if (x != -1 && y != -1)
		{
			p[k].x = x;
			p[k].y = y;
			p[k].lable = lable;
			k++;
		}
		else
		{
			lable++;
		}
	}

	for (i = 0; i < k; i++)
	{
		dis[i][i] = 0;
		for (j = i + 1; j < k; j++)
		{
			tmpdis = calcdis(i, j);
			if (p[i].lable == p[j].lable && i + 1 == j)
			{
				dis[i][j] = dis[j][i] = tmpdis / FAST;
			}
			else
			{
				dis[i][j] = dis[j][i] = tmpdis / SLOW;
			}
		}
	}

	DIJ(k);

/*	for (i = 0; i < k; i++)
	{
		printf("%.2lf\n", mindis[i]);
	}
*/	return 0;
}