文章

3

粉丝

0

获赞

3

访问

76

头像
Freckles 题解:C语言/prime解法
P1183 北京大学上机题
发布于2026年3月29日 17:40
阅读数 17

#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 <=...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发