2820329_ac_60ms_804k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#define INF 2100000000

struct point
{
	int x, y;
};

point pt[300];
int no;
double map[301][301];
double dist[301];

int get_id(point t)
{
	int i;

	for(i = 0; i < no; i++)
	{
		if(t.x==pt[i].x&&t.y==pt[i].y)
			return i;
	}
	pt[no] = t;
	return no++;
}

double min(double a,double b)
{
	return a-b>0?b:a;
}

double dis(int a,int b)
{
	return sqrt((pt[a].x-pt[b].x)*(pt[a].x-pt[b].x)+(pt[a].y-pt[b].y)*(pt[a].y-pt[b].y));
}

void dijkstra()
{
    int i, j, w;
	int s[301];

    for(i = 1; i <= no; i++)
	{
        dist[i] = map[i][0];
        s[i] = 0;
    }
    s[0] = 1;dist[0] = 0;
    for(i = 0; i < no-1; i++)
	{
        double min = INF;
        int u;
        for(j = 0; j < no; j++)
		{
            if(!s[j]&&dist[j]<min)
			{
                u = j;
                min = dist[j];
            }
        }
        s[u] = 1;
        for(w = 0; w < no; w++)
		{
            if(!s[w] &&  map[u][w] < INF && dist[w]>map[u][w]+dist[u])
			{
                dist[w] = map[u][w]+dist[u];
            }
        }
    }
	printf("%.0lf\n",dist[no-1]);
}

int main()
{
	int i, j;
	int id, n;
	int line[201];
	point st, ed, tmp;

	scanf("%d%d%d%d",&st.x,&st.y,&ed.x,&ed.y);
	no = 0;
	pt[no++] = st;
	for(i = 0; i < 300; i++)
		for(j = 0; j < 300; j++)
			map[i][j] = INF;
	while(scanf("%d%d",&tmp.x,&tmp.y)==2)
	{
		n = 0;
		while(tmp.x!=-1&&tmp.y!=-1)
		{
			id = get_id(tmp);
			line[n++] = id;
			scanf("%d%d",&tmp.x,&tmp.y);
		}
		for(i = 1; i < n; i++)
		{
			map[line[i-1]][line[i]] = dis(line[i-1],line[i])*60.0/40000.0;
			map[line[i]][line[i-1]] = map[line[i-1]][line[i]];
		}
	}
	get_id(ed);
	for(i = 0; i < no; i++)
		for(j = i+1; j < no; j++)
		{
			map[i][j] = min(60.0*dis(j,i)/10000.0,map[i][j]);
			map[j][i] = map[i][j];
		}
	dijkstra();
	return 1;
}