> #include<stdio.h>
> #include<math.h>
> 
> #define MAX 800
> #define MAX_VALUE 100000000
> 
> struct _node
> {
> 	int x;
> 	int y;
> };
> 
> struct _aaa
> {
> 	int s;
> 	int e;
> };
> 
> struct _bbb
> {
> 	int pre;
> 	float we;
> };
> 
> typedef struct _aaa aaa;
> typedef struct _bbb bbb;
> typedef struct _node node;
> 
> bbb flag[MAX];
> node town[MAX];
> float map[MAX][MAX];
> aaa result[MAX];
> 
> int town_count = 0;
> int exist = 0;
> int start = 0;
> 
> int main(void)
> {
> 	int i = 0;
> 	int j = 0;
> 	
> 	scanf("%d",&town_count);
> 
> 	for(i = 0; i < town_count; ++i)
> 	{
> 		scanf("%d %d",&town[i].x,&town[i].y);
> 	}
> 
> 	for(i = 0; i < town_count; ++i)
> 	{
> 		for(j = 0; j < town_count; ++j)
> 		{
> 			if( i == j )
> 			{
> 				map[i][j] = 0;
> 				continue;
> 			}
> 
> 			map[i][j] = (float)sqrt( ( town[i].x - town[j].x ) * ( town[i].x - town[j].x ) +  ( town[i].y - town[j].y ) * ( town[i].y - town[j].y ) );
> 		}
> 	}
> 
> 	scanf("%d",&exist);
> 
> 	for(i = 0; i < exist; ++i)
> 	{
> 		int x = 0;
> 		int y = 0;
> 		scanf("%d %d",&x,&y);
> 		map[x-1][y-1] = 0.01f;
> 		map[y-1][x-1] = 0.01f;
> 		start = x - 1;
> 	}
> 
> 
> 	for(i = 0; i < town_count; ++i)
> 	{
> 		flag[i].pre = start;
> 		flag[i].we = map[i][start];
> 	}
> 
> 	flag[start].we = 0;
> 	
> 	float min = 0;
> 	int k = -1;
> 	int len = 0;
> 
> 	for(i = 0; i < town_count - 1; ++i)
> 	{
> 		min = MAX_VALUE;
> 		for(j = 0; j < town_count; ++j)
> 		{
> 			if( flag[j].we != 0 && flag[j].we < min )
> 			{
> 				min = flag[j].we;
> 				k = j;
> 			}
> 		}
> 		
> 		if( map[k][flag[k].pre] - 0.01 > 0 )
> 		{
> 			result[len].s = flag[k].pre;
> 			result[len].e = k;
> 			++len;
> 		}
> 
> 		for(j = 0; j < town_count; ++j)
> 		{
> 			if( map[j][k] < flag[j].we )
> 			{
> 				flag[j].we = map[j][k];
> 				flag[j].pre = k;
> 			}
> 		}
> 	}
> 	
> 	for(i = 0; i < len; ++i)
> 	{
> 		printf("%d %d\n",result[i].e + 1,result[i].s + 1);
> 	}
> 	
> 
> 	return 0;
> }

• Re:总有人前赴后继的贴代码,,,,FT,,,不知是炫耀还是.... (6) luoguangyao 2009-03-22 14:06:17
  • 写的又长又难看还好意思来贴。 (2) jiangmingh 2009-05-10 20:26:30