新年好(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/ 在环形道路上,矗立着一串加油站,宛如等待挑战的谜题。这条路上的每个加油站都有一桶汽油,而开车到下一…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
多元隐函数 偏导公式
我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式,给定一个隐函数关系: F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 🧠 目标: 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z、 …...
基于单片机的宠物屋智能系统设计与实现(论文+源码)
本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢,连接红外测温传感器,可实时精准捕捉宠物体温变化,以便及时发现健康异常;水位检测传感器时刻监测饮用水余量,防止宠物…...
CppCon 2015 学习:Simple, Extensible Pattern Matching in C++14
什么是 Pattern Matching(模式匹配) ❝ 模式匹配就是一种“描述式”的写法,不需要你手动判断、提取数据,而是直接描述你希望的数据结构是什么样子,系统自动判断并提取。❞ 你给的定义拆解: ✴ Instead of …...
