新年好(Dijkstra+dfs/全排列)
1135. 新年好 - AcWing题库


思路: 1.先预处理出1,a,b,c,d,e到其他点的单源最短路,也就是进行6次Dijkstra
2.计算以1为起点的这6个数的全排列,哪种排列方式所得距离最小,也可以使用dfs
1.Dijkstra+dfs
#define int long longusing namespace std;typedef pair<int,int> PII;constexpr int N =2e5+5;
int dist[6][N];
bool st[50005];
int n,m,h[N],w[N],ne[N],e[N],idx;
int rela[N];
int ans;void add(int a,int b,int c)
{e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}void Dijkstra(int s, int dist[])
{memset(dist, 0x3f, N*4);//int是4字节,所以大小就是4*Nmemset(st,0,sizeof st);dist[s]=0;priority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({0,s});while(heap.size()){auto [c,t] = heap.top();heap.pop();if(st[t]) continue;st[t]=true;for(int i=h[t];~i;i=ne[i]){int j=e[i];if(dist[j]>c+w[i]){dist[j]=c+w[i];heap.push({dist[j],j});}}}
}int dfs(int u,int num,int dis)
{if (num==6){return dis;}int ret=0x3f3f3f3f;for (int i=1;i<=5;i++){if (!st[i]){st[i] = 1;ret = min(ret,dfs(i,num+1,dis+dist[u][rela[i]]));st[i] = 0;}}return ret;
}void solve()
{cin>>n>>m;rela[0]=1;for(int i=1;i<=5;i++){cin>>rela[i];}memset(h,-1,sizeof h);while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);}for(int i=0;i<=5;i++){Dijkstra(rela[i],dist[i]);}memset(st,false,sizeof st);cout<<dfs(0,1,0);
}int32_t main()
{int t;//cin>>t;t=1;while(t--) solve();
}
2.Dijkstra+全排列
#define int long longusing namespace std;typedef pair<int,int> PII;constexpr int N =2e5+5;
int dist[6][N];
bool st[50005];
int n,m,h[N],w[N],ne[N],e[N],idx;
int rela[N],order[6];
int ans;void add(int a,int b,int c)
{e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}void Dijkstra(int s, int dist[])
{memset(st,0,sizeof st);dist[s]=0;priority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({0,s});while(heap.size()){auto [c,t] = heap.top();heap.pop();if(st[t]) continue;st[t]=true;for(int i=h[t];~i;i=ne[i]){int j=e[i];if(dist[j]>c+w[i]){dist[j]=c+w[i];heap.push({dist[j],j});}}}
}void solve()
{memset(dist,0x3f,sizeof dist);cin>>n>>m;order[0]=0;rela[0]=1;for(int i=1;i<=5;i++){order[i]=i;cin>>rela[i];}memset(h,-1,sizeof h);while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);}for(int i=0;i<=5;i++){Dijkstra(rela[i],dist[i]);}memset(st,false,sizeof st);ans=0x3f3f3f3f;do{if(order[0]!=0) break;int sum=dist[0][rela[order[1]]];for(int i=1;i+1<=5;i++)sum+=dist[order[i]][rela[order[i+1]]];ans=min(ans,sum);}while(next_permutation(order,order+6));cout<<ans;
}int32_t main()
{int t;//cin>>t;t=1;while(t--) solve();
}
相关文章:
新年好(Dijkstra+dfs/全排列)
1135. 新年好 - AcWing题库 思路: 1.先预处理出1,a,b,c,d,e到其他点的单源最短路,也就是进行6次Dijkstra 2.计算以1为起点的这6个数的全排列,哪种排列方式所得距离最小,也可以使用dfs 1.Dijkstradfs #define int long longusing …...
如何“看到” Spring 容器?
Spring 容器是一个运行时的抽象工具,用来管理 Bean 的生命周期和依赖。虽然它本身不可直接观察,但可以通过以下方式间接“看到”容器的内容或行为。 2.1 容器是如何实例化的? Spring 容器的实例化是通过 ApplicationContext 或 BeanFactory …...
怎么使用CRM软件?操作方法和技巧有哪些?
什么是CRM? 嘿,大家好!你知道吗,在当今这个数字化时代里,我们每天都在与各种各样的客户打交道。无论是大公司还是小型企业,都希望能够更好地管理这些关系并提高业务效率。这时候就轮到我们的“老朋友”——…...
Spingboot整合Netty,简单示例
Netty介绍在文章末尾 Netty介绍 项目背景 传统socket通信,有需要自身管理整个状态,业务繁杂等问题。 pom.xml <dependency><groupId>io.netty</groupId><artifactId>netty-all</artifactId><version>4.1.117.F…...
grafana新增email告警
选择一个面板 比如cpu 新增一个临界点表达式 input选A 就是A的值达到某个临界点 触发告警 我这边IS ABOVE0.15就是cpu大于0.15%就触发报警,这个值怎么填看指标的值显示 这里要设置一下报警条件 这边随便配置下 配置标签和通知,选择你的邮件 看下告警…...
Github 2025-01-20 开源项目周报 Top15
根据Github Trendings的统计,本周(2025-01-20统计)共有15个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Python项目10Rust项目2TypeScript项目1C++项目1Jupyter Notebook项目1Go项目1Tabby: 自托管的AI编码助手 创建周期:310 天开发语言:Rust协议类…...
【Rabbitmq】Rabbitmq高级特性-发送者可靠性
Rabbitmq发送者可靠性 发送者重连发送者确认1.开启确认机制2.ReturnCallback3.ConfirmCallback MQ的可靠性数据持久化交换机持久化队列持久化消息持久化 Lazy Queue 总结其他文章 Rabbitmq提供了两种发送来保证发送者的可靠性,第一种叫发送者重连,第二种…...
K8S中Service详解(一)
Service介绍 在Kubernetes中,Service资源解决了Pod IP地址不固定的问题,提供了一种更稳定和可靠的服务访问方式。以下是Service的一些关键特性和工作原理: Service的稳定性:由于Pod可能会因为故障、重启或扩容而获得新的IP地址&a…...
Effective C++读书笔记——item23(用非成员,非友元函数取代成员函数)
一、主要观点: 在某些情况下,使用 non-member、non-friend 函数来替换 member 函数可以增强封装性和可扩展性,提供更好的软件设计。 二、详细解释: 封装性: 类成员函数的封装性考量:成员函数可以访问类的…...
云原生前端开发:打造现代化高性能的用户体验
引言:前端开发的新风向 在过去的几年中,前端开发领域经历了快速的演变,从早期的静态网页到如今复杂的单页应用(SPA),再到微前端架构和渐进式Web应用(PWA),前端技术一直处…...
循环队列(C语言版)
循环队列(C语言版) 1.简单介绍循环队列2.使用何种结构来实现3.基本结构4.初始化5.判空判满6.向循环队列插入一个元素7.从循环队列中删除一个元素8.获取队头队尾元素9.释放空间10.完整代码 🌟🌟hello,各位读者大大们你们好呀&#…...
考研408笔记之数据结构(五)——图
数据结构(五)——图 1. 图的基本概念 1.1 图的定义 1.2 有向图和无向图 在有向图中,使用圆括号表示一条边,圆括号里元素位置互换没有影响。 在无向图中,使用尖括号表示一条边,尖括号里元素位置互换则表示…...
没有公网IP实现seafile本地IP访问和虚拟局域网IP同时访问和上传文件
前言 Ubuntu 24.04 LTSDocker 安装 seafileOpenWrtTailscale Ubuntu 24.04 LTS 通过 docker desktop 安装 seafile 搭建个人网盘中,已经实现了本地局域网放问Ubuntu IP来访问Seafile,以及通过 Ubuntu 的 Tailscale IP 访问Seafile。但是,文…...
【Hadoop面试题2025】
文章目录 简单题故障及相应的处理方法中等难度高难度小文件小文件的产生小文件问题的影响小文件治理方案推荐方案 冷文件冷文件的产生冷文件问题的影响冷文件治理方案推荐方案 简单题 一、基础概念类 什么是Hadoop? 答案:Hadoop是一个开源的分布式计算框…...
2000-2010年各省第三产业就业人数数据
2000-2010年各省第三产业就业人数数据 1、时间:2000-2010年 2、来源:统计年鉴、各省年鉴 3、指标:行政区划代码、地区、年份、第三产业就业人员数(万人) 4、范围:31省 5、指标解释:第三产业…...
第十一讲 多线程
多线程是提升程序性能非常重要的一种方式,也是Java编程中的一项重要技术。在程序设计中,多线程就是指一个应用程序中有多条并发执行的线索,每条线索都被称作一个线程,它们会交替执行,彼此间可以进行通信。 1. 进程与线…...
VUE之路由Props、replace、编程式路由导航、重定向
目录 1、路由_props的配置 2、路由_replaces属性 3、编程式路由导航 4、路由重定向 1、路由_props的配置 1)第一种写法,将路由收到的所有params参数作为props传给路由组件 只能适用于params参数 // 创建一个路由器,并暴露出去// 第一步…...
windows安装ES
1. 下载ES 访问ES官网下载Download Elasticsearch | Elastic 2. 配置环境变量 ES_JAVA_HOME : D:\jdk-17.0.9 ES_HOME : D:\elasticsearch-8.17.1-windows-x86_64\elasticsearch-8.17.1 3. 添加一些ES的配置 <1>关闭ES安全认证 打开elasticsearch-8.17.1\config\e…...
论文速读|Multi-Modal Disordered Representation Learning Network for TBPS.AAAI24
论文地址:Multi-Modal Disordered Representation Learning Network for Description-Based Person Search 代码地址:未开源(2025.01.22) bib引用: inproceedings{yang2024multi,title{Multi-Modal Disordered Repres…...
小哆啦解题记:加油站的奇幻冒险
小哆啦解题记:加油站的奇幻冒险 小哆啦开始力扣每日一题的第十三天 https://leetcode.cn/problems/gas-station/description/ 在环形道路上,矗立着一串加油站,宛如等待挑战的谜题。这条路上的每个加油站都有一桶汽油,而开车到下一…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
