prim+堆优化——公路修建_c++ 公路修建 prim 堆优化-程序员宅基地

技术标签： prim

原文链接：https://www.luogu.com.cn/problem/P1265

在这里插入图片描述

AC代码：

#include<iostream>
#include<string.h>
#include<vector>
#include<math.h>
#include<iomanip>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
int n,visit[5005],num=0;
double lowc[5005],inf=1e9,amount=0;
typedef struct node{
    
	double x,y;
}node;
node nod;
vector<node> vec;
typedef struct edge{
    
	int id;double w;
	bool operator <(const edge &a) const{
    
		return a.w<w;
	}
}edge;
edge edg,edg1;
priority_queue<edge> que;
double calc(int n0,int n1){
    
	double dis=(vec[n0].x-vec[n1].x)*(vec[n0].x-vec[n1].x)+(vec[n0].y-vec[n1].y)*(vec[n0].y-vec[n1].y);
	dis=sqrt(dis);
	return dis;
}
void prim(){
    
	int i,j;
	lowc[0]=0;
	edg.id=0;edg.w=0;
	que.push(edg);
	while(!que.empty()){
    
		edg=que.top();que.pop();
		if(visit[edg.id]==1) continue;
		visit[edg.id]=1;
		num++;
		amount+=edg.w;
		if(num==n) return ;
		for(i=0;i<n;i++){
    
			if(visit[i]==1) continue;//cout<<calc(edg.id,i)<<endl;
			if(lowc[i]>calc(edg.id,i)){
    
				lowc[i]=calc(edg.id,i);
				edg1.id=i;edg1.w=lowc[i];
				que.push(edg1);//cout<<i<<" "<<lowc[i]<<endl;
			}
		}
	}
}
int main(){
    
	int i,j;
	cin>>n;
	for(i=0;i<5005;i++){
    
		visit[i]=0;
		lowc[i]=inf;
	}
	for(i=0;i<n;i++){
    
		cin>>nod.x>>nod.y;
		vec.push_back(nod);
	}
	prim();
	cout<<setiosflags(ios::fixed)<<setprecision(2);
	cout<<amount<<endl;
	return 0;
}

本文链接：https://blog.csdn.net/qq_40892316/article/details/105381805

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

【HTML网页设计】 HTML+CSS+JavaScript+jquery仿慕课网教学培训网站设计实例企业网站制作_javascript、 jquery技术的网页-程序员宅基地

文章浏览阅读880次，点赞22次，收藏22次。常见网页设计作业题材有个人、美食、公司、学校、旅游、电商、宠物、电器、茶叶、家居、酒店、舞蹈、动漫、服装、体育、化妆品、物流、环保、书籍、婚纱、游戏、节日、戒烟、电影、摄影、文化、家乡、鲜花、礼品、汽车、其他等网页设计题目, A+水平作业, 可满足大学生网页大作业网页设计需求都能满足你的需求。原始HTML+CSS+JS页面设计, web大学生网页设计作业源码，画面精明，排版整洁，内容丰富，主题鲜明，非常适合初学者学习使用。精彩专栏_javascript、 jquery技术的网页

Spring-全面详解（学习总结）-程序员宅基地

文章浏览阅读10w+次，点赞2.1k次，收藏1.3w次。Spring1.简介1.1.简介简介Spring : 春天 —>给软件行业带来了春天2002年，Rod Jahnson首次推出了Spring框架雏形interface21框架。2004年3月24日，Spring框架以interface21框架为基础，经过重新设计，发布了1.0正式版。很难想象Rod Johnson的学历 , 他是悉尼大学的博士，然而他的专业不是计算机，而是音乐学。Spring理念 : 使现有技术更加实用 . 本身就是一个大杂烩 , 整合现有的框架技术官网 : ht_spring

Git||02Git bash-外扩tree的安装与使用教程_=使用gitbash tree-程序员宅基地

文章浏览阅读1.1k次。02Git bash-外扩tree的安装与使用教程简介：在Windows下的Git Bash环境下安装tree工具与使用，很多大佬都标注了怎么安装，但是没有具体到怎么来使用，所以我来补充一下使用（怕你们不放心文件链接我就在CSDN也上传一个）其实最简单的方法是输入这个，连插件都不用装：但是这种方法不支持一些其他操作，所以我们可以往git文件夹里塞一个tree（或许叫它插件？）然后就能用命令..._=使用gitbash tree

DDD系列 - 第0讲 DDD中常提到的应用架构总结（六边形、洋葱、整洁、清晰）_整洁架构六边形架构-程序员宅基地

文章浏览阅读5.5k次，点赞14次，收藏36次。最近在学习DDD应用架构设计时，接触到了不同的应用架构设计概念，如六边形架构、洋葱架构、整洁架构、清晰架构...，起初是一头雾水，在不断学习过程中也算对此有了些理解，故在本文中对这些架构进行了简单的介绍和总结。............_整洁架构六边形架构

积少成多Flash ActionScript 3.0(5) - 实例之闹钟(自定义事件, 画图, 动画)_积少成多flash(5) - actionscript 3.0 实例之闹钟(自定-程序员宅基地

文章浏览阅读678次。[源码下载]积少成多Flash ActionScript 3.0(5) - 实例之闹钟(自定义事件, 画图, 动画)作者：webabcd介绍通过一个经典示例，即闹钟，对使用Flash ActionScript 3.0画图、做动画有一个大概的了解，并通过此示例学习自定义事件的开发自定义事件 - 继承自 Event ，一个 public static const 定义事件类型，其他 publ_积少成多flash(5) - actionscript 3.0 实例之闹钟(自定

趣谈Linux操作系统随笔——4.0 系统调用：公司成立好了就要开始接项目-程序员宅基地

文章浏览阅读247次。系统调用：公司成立好了就要开始接项目软件平台：运行于VMware Workstation 12 Player下UbuntuLTS16.04_x64 系统开发环境：Linux-4.19-rc3内核，glibc-2.9目录系统调用：公司成立好了就要开始接项目1、系统调用的封装——glibc2、32位系统调用过程2.1 执行32位对应的`DO_CALL`2.2 在DO_CALL中陷入内核ENTER_KERNEL2.3 小结3、64位系统调用过程3.1 执行64位对应的`DO_CALL`3.2 在`._公司成立好了就要开始接项目

随便推点

SQL数据库更改SQL Sever身份认证_ef改成sql server身份验证-程序员宅基地

文章浏览阅读859次。欢迎来到unity学习、unity培训这里有很多U3D资源、U3D培训视频、U3D教程、U3D常见问题、U3D项目源码，我们致力于打造业内unity3d培训、学习第一品牌SQL数据库更改SQL Sever身份认证今天我也没有学到什么，一天都在找地形资源，要不就是不能有，要不就是自带的代码有问题，以后再也不自己找资源走东西了。好了，今天还是回忆一下以前_ef改成sql server身份验证

【0-1背包问题】遗传算法 python 完整代码可直接运行_遗传算法解决0-1背包问题 python-程序员宅基地

文章浏览阅读2k次。python 0-1背包问题遗传算法完整代码直接运行_遗传算法解决0-1背包问题 python

Uncaught (in promise) TypeError: fullscreen error-程序员宅基地

文章浏览阅读1.3w次，点赞11次，收藏2次。https://blog.csdn.net/weixin_42532454/article/details/89882568浏览器是否支持全屏console.log(document.fullscreenEnabled)如果不支持全屏看下是不是iframe嵌套引起来的解释：我后来发现我的页面是在iframe框架中使用的并且没有设置allowfullscreen="true"属性；解决方案：设置allowfullscreen="true"属性，就解决了。..._uncaught (in promise) typeerror: fullscreen error

【PaperReading】TERA: Self-Supervised Learning of Transformer Encoder Representation for Speech-程序员宅基地

文章浏览阅读407次。Title：TERA: Self-Supervised Learning of Transformer Encoder Representation for SpeechWhat’s main claim? Key idea?This paper introduces a self-supervised speech pre-training method called TERA. The authors use a multi-target auxiliary task to pre-train _tera: self-supervised learning of transformer encoder representation for spe

gradle springboot单元测试报错No tests found for given includes,_gradle no tests found for given includes:-程序员宅基地

文章浏览阅读1.6k次。gradle springboot单元测试报错No tests found for given includes,具体错误见下图解决办法，如下图settings的gradle配置Run test using Intellij IDEA，项目的workspace.xml新增<property name="dynamic.classpath" value="true" />..._gradle no tests found for given includes:

TSP问题的各种解法（Python）_人工蜂群tsp问题python-程序员宅基地

文章浏览阅读3.4k次，点赞2次，收藏55次。#coding=utf-8import matplotlib.pyplot as pltimport mathimport timeimport randomx = [4475,4475,4475,4475,5450,5475,5475,4575,5425,5425,5425,5425,5425,6000,6375,6000,6375,6475,6475,6475,6475,6100,6350,6350,6100,6550,5775,6075,6375,6375,6075,5775,6975,_人工蜂群tsp问题python