首页 > 代码库 > 杭电1162Eddy's picture
杭电1162Eddy's picture
Eddy‘s picture
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 28 Accepted Submission(s) : 17
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Problem descriptions as follows: Given you some coordinates pionts on a drawing paper, every point links with the ink with the straight line, causes all points finally to link in the same place. How many distants does your duty discover the shortest length which the ink draws?
Input
Input contains multiple test cases. Process to the end of file.
Output
Sample Input
3 1.0 1.0 2.0 2.0 2.0 4.0
Sample Output
3.41
这道题也是很简单的最短路径问题
代码:
#include<stdio.h>
#include<string.h>
#include<math.h>
#define INF 1 << 30
double a[101] , b[101] , map[101][101] ;
double dis[101] ;
int used[101] ;
void prim(int n)
{
int c = 0 ;
int i = 0 , j = 0 ;
double sum = 0 ;
dis[1] = 0 ;
for(i = 1 ; i <= n ; i++)
{
double min = INF ;
c = 0 ;
for(j = 1 ; j <= n ; j++)
{
if(!used[j] && dis[j] < min)
{
min = dis[j] ;
c =j ;
}
}
used[c] = 1 ;
for(j = 1 ; j <= n ; j++ )
{
if(!used[j] && dis[j] > map[c][j])
dis[j] = map[c][j] ;
}
}
for(i = 1 ; i <= n ; i++)
sum += dis[i] ;
printf("%.2lf\n",sum);
}
int main()
{
int n = 0 ;
while(~scanf("%d",&n))
{
memset(a , 0 , sizeof( a ) ) ;
memset(b , 0 , sizeof( b ) ) ;
int i = 0 , j = 0 ;
for(i = 1 ; i <= n ; i++)
{
for(j = 1 ; j <= n ; j++)
map[i][j] = INF ;
dis[i] = INF ;
used[i] = 0 ;
}
for(i = 1 ; i <= n ; i++)
{
scanf("%lf%lf" , &a[i] , &b[i] );
}
double m = 0 , x = 0;
for(i = 1 ; i <= n ; i++ )
{
for(j = 1 ; j <= n ; j++)
{
x = (a[j]-a[i])*(a[j]-a[i])+(b[j]-b[i])*(b[j]-b[i]) ;
m = sqrt( x ) ;
map[i][j] = map[j][i] = m ;
}
}
prim( n );
}
return 0 ;
}
杭电1162Eddy's picture