#include<iostream>
#include<cmath>

using namespace std;

#define MAX 1000
#define INF 100000000

struct E
{
	double x, y;
	int kind;
}; E eduge[MAX];

double G[MAX][MAX];      //切记 定义double

double Dij(int n,int s,int t)
{
	int i,j,w,mark[MAX];
	double minc,d[MAX];
	for (i=0;i<n;i++) {
		mark[i]=0;
		d[i]=G[s][i];
	}
	mark[s]=1;d[s]=0;
	for (i=1;i<n;i++)
	{
		minc=INF;
		w=0;
		for (j=0;j<n;j++)
			if ((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}
			mark[w]=1;
		for (j=0;j<n;j++)
			if ((mark[j]==0)&&(G[w][j]!=INF)&&(d[j]>d[w]+G[w][j]))
				d[j]=d[w]+G[w][j];
	}
	return d[t];
}

double dis(E p1, E p2)
{
	return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

int main()
{
	double bx, by, ex, ey;
	double tempx, tempy;
	int i, j;
	scanf("%lf%lf%lf%lf", &bx, &by, &ex, &ey);         //原来只有一组数据- -
	memset(eduge, 0, sizeof(eduge));
	eduge[0].x = bx, eduge[0].y = by, eduge[0].kind = 0;
	eduge[1].x = ex, eduge[1].y = ey, eduge[1].kind = 1;
	int gg = 2;
	int k = 1; //表示不同的线路
	while(scanf("%lf%lf", &tempx, &tempy) != EOF) {
		k ++;
		eduge[gg].x = tempx, eduge[gg].y = tempy, eduge[gg ++].kind = k;
		while(scanf("%lf%lf", &tempx, &tempy) && tempx != -1)
			eduge[gg].x = tempx, eduge[gg].y = tempy, eduge[gg ++].kind = k;
	}
	for(i = 0; i < MAX; i ++)
		for(j = 0; j <= i; j ++)
			if(i == j)
				G[i][j] = 0;
			else
				G[i][j] = G[j][i] = INF;
	for(i = 0; i < gg; i ++)
		for(j = 0; j < i; j ++) {
			if(eduge[i].kind == eduge[j].kind)
				G[i][j] = G[j][i] =  dis(eduge[i], eduge[j]) * 3 / 2000;
			else
				G[i][j] = G[j][i] =  dis(eduge[i], eduge[j]) * 3 / 500;
		}
	printf("%.0lf\n", Dij(gg, 0, 1));

	return 0;
}

• 坚信系统问题- - (0) allen4053040allen 2010-06-02 11:26:11
  • http://zhidao.baidu.com/question/157000415.html?push=keyword (0) 20053565 2010-06-03 10:19:22
    • 找到一个很牛B的错误。。。唉- - (0) allen4053040allen 2010-06-03 12:34:01
      • 以后不要随便怀疑系统哦~ (0) 20053565 2010-06-03 14:16:03
        • 我的错…… (0) allen4053040allen 2010-06-05 10:59:35