文章
3
粉丝
0
获赞
3
访问
76
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define M 105
#define INF 1e12
typedef struct node {
double x;
double y;
}Node;
double dist[M];
Node list[M];
int visited[M];
double calc_dist(Node a, Node b) {//计算距离
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
int main() {
int n;
while (scanf("%d", &n) != EOF && n != 0) {
for (int i = 1; i <= n; i++) {//节点从1开始编码到N
double x, y;
scanf("%lf%lf", &x, &y);
list[i] = (Node){ x,y };
}
memset(visited, 0, sizeof(visited));//初始化很重要!!
memset(dist, INF, sizeof(dist));
//从第一个节点开始prime,计算到邻居的距离
for (int i = 1; i <= n; i++) {
dist[i] = calc_dist(list[1], list[i]);
}
visited[1] = 1;
dist[1] = 0;
//从剩余的节点中,取出间距最小的邻居,并更新邻居的邻居
double cost = 0;
for (int i = 1; i < n; i++) {
int min_idx = -1;
double min_dist = INF;
for (int j = 1; j <=...
登录后发布评论
暂无评论,来抢沙发