发布时间:2026/8/21 10:34:48
2026萌新联赛第三场(郑州轻工业大学)(F魔法传送门)Dijkstra算法(图的最短路径)迪杰斯特拉算法 Dijkstra算法(图的最短路径)初始 起点adista0其余∞第1轮 选b(2)更新c3、d5集合{a,b}第2轮 选c(3)更新e7、f4集合{a,b,c}第3轮 选f(4)无更新集合{a,b,c,f}第4轮 选d(5)更新e6集合{a,b,c,f,d}第5轮 选e(6)无更新全节点完结 最终最短距离 b2c3d5e6f4时间复杂度堆优化版:O(mlogn) --用优先队列快速取出距离最小的节点适合稀疏图暴力版:O(n*n) --适合节点少的稠密图适用范围求解单源最短路径(一个起点到其余的节点)硬性要求:所有边权0(存在负边权用SPFA)核心思想dist[i]:起点到节点i的已知最短距离初始化除了起点外全部设为无穷大用小根堆每次取出当前距离最小的未确定的节点对该节点所有邻边做松弛:若dist[v]dist[u]w 就更新dist[v]并堆入堆vis[i]标记节点最短路径已确定避免后续重复n:节点总数m:边总数数组作用g[]邻接表存图稀疏图首选比邻接矩阵省空间dist[]动态维护起点到每个节点的最短距离vis[]标记节点是否拿到最终最短路避免重复计算分层 Dijkstra最多 k 次免费 / 减半边权路径回溯新增pre[]数组存前驱节点反向还原路线多起点最短路初始把所有起点同时入堆即可[P4779 【模板】单源最短路径标准版 - 洛谷][(https://www.luogu.com.cn/problem/P4779)#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define PLL pairll, ll #define YES coutYESendl; #define NO coutNOendl; using namespace std; const ll INF1e15; const ll MAXN100005; vectorPLLg[MAXN]; //邻接表:g[u]{v,边权w} ll dist[MAXN];//最短距离 bool vis[MAXN]; void dijkstra(ll start,ll n) { for(ll i1;in;i) { dist[i]INF; } // memset(vis,0,sizeof(vis)); dist[start]0; priority_queuePLL,vectorPLL,greaterPLLq; q.push({0,start}); //{距离节点编号}初始状态传入 while(!q.empty()) { PLL curq.top(); ll dcur.fi; ll ucur.se; q.pop(); if(ddist[u]) { continue; } for(auto edge:g[u]) { ll vedge.fi; ll wedge.se; if(dist[v]dw) { dist[v]dw; q.push({dist[v],v}); } } } } int main() { IOS ll n,m,s; cinnms; for(ll i1;iMAXN;i) { g[i].clear(); } for(ll i1;im;i) { ll u,v,w; cinuvw; g[u].emplace_back(v,w);//有向图 // g[v].emplace_back(u,w); //无向图 } dijkstra(s,n); for(ll i1;in;i) { if(i!n) { coutdist[i] ; } else { coutdist[i]; } } coutendl; // coutfixedsetprecision(x) ; return 0; }F-魔法传送门_河南萌新联赛2026第三场郑州轻工业大学核心:将用多少次魔法加入状态中两种转移遍历 u 的每条边 u‑v边权 w假设现在状态在 u已用 j 次魔法当前距离 d转移 1不使用魔法留在同一层老老实实付边权 w 走到 v魔法次数不变。dis[v][j] d w 如果满足更新把 (dw , v , j) 丢进优先队列。转移 2使用本次魔法跳到下一层仅当 jk这条边直接免费不需要加 w魔法次数 1(j1)。dis[v][j1] d 如果满足更新把 (d , v , j1) 丢进优先队列。只有 jk 才能做这个转移不能超过允许的 k 次#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define PLL pairll, ll #define YES coutYESendl; #define NO coutNOendl; using namespace std; typedef pairll,pairll,llP; const ll INF1e18; const ll MAXN100005; using namespace std; ll n,m,k; vectorPLLg[1005]; ll dis[1005][15];//距离魔法 int main() { IOS cinnmk; for(ll i1;im;i) { ll u,v,w; cinuvw; g[u].emplace_back(v,w); g[v].emplace_back(u,w); } for(ll i1;in;i) { for(ll j0;jk;j) { dis[i][j]INF; } } dis[1][0]0; priority_queueP,vectorP,greaterPq; q.push({0,{1,0}}); while(!q.empty()) { auto nowq.top(); q.pop(); ll dnow.fi; ll unow.se.fi; ll usednow.se.se; if(ddis[u][used]) { continue; } for(auto edge :g[u]) { ll vedge.fi; ll wedge.se; if(dis[v][used]dw) { dis[v][used]dw; q.push({dis[v][used],{v,used}}); } if(usedkdis[v][used1]d) { dis[v][used1]d; q.push({dis[v][used1],{v,used1}}); } } } ll ansINF; for(ll j0;jk;j) { ansmin(ans,dis[n][j]); } coutansendl; // coutfixedsetprecision(x) ; return 0; }

相关新闻

2026/8/21 10:34:48

AI自动化办公实战:基于Harness、Workbuddy与Codex构建智能工作流

在实际工作中,重复性的文档处理、数据整理、信息查询和跨系统操作占据了大量时间。Harness、Workbuddy 和 Codex 这类 AI 工具的出现,为自动化办公提供了新的思路。它们并非简单的脚本工具,而是通过理解自然语言指令,直接操作软件…

2026/8/21 10:34:48

“工业原生”这四个字,正在被越来越多人抢

2026年6月29日,优艾智合在上海发布工业具身智能大模型"FabriX",同步推出"工业原生人形机器人"隙锋——注意这个词:工业原生。不到一个月后的7月24日,SeptMind在上海中心发布工业物理AI平台,创始人…

2026/8/21 10:34:48

二乙二醇丁醚 DB 供应商该如何筛选?

二乙二醇丁醚 DB,俗称大防白水,是醇醚体系内应用十分广泛的高沸点溶剂,依靠优秀的偶联性、慢挥发特性,大量用于工业涂料、丝印油墨、PCB 线路板油墨、金属清洗、水性体系调配等领域。随着下游制造业对原料稳定性要求持续提升&…

2026/8/21 11:51:35

AI Agent 面试题 389:Agent的工作记忆容量优化策略有哪些?

🔥 AI Agent 面试题 389:Agent的工作记忆容量优化策略有哪些?摘要:本文深入解析了「Agent的工作记忆容量优化策略有哪些?」这一 AI Agent 领域的核心面试题。文章从 工作记忆 的基本概念出发,系统性地剖析了…

2026/8/21 11:51:35

从零构建生产级RAG系统:LangGraph编排与LoRA微调实战

如果你正在构建一个基于大语言模型(LLM)的智能应用,比如一个能回答公司内部文档问题的客服机器人,或者一个能总结长篇技术报告的工具,你很可能已经遇到了一个核心难题: 大模型无法记住它没“见过”的信息&…

2026/8/21 11:51:35

AI Agent 面试题 388:如何实现Agent工作记忆的结构化存储?

🔥 AI Agent 面试题 388:如何实现Agent工作记忆的结构化存储?摘要:本文深入解析了「如何实现Agent工作记忆的结构化存储?」这一 AI Agent 领域的核心面试题。文章从 工作记忆 的基本概念出发,系统性地剖析了…

2026/8/21 11:51:35

996引擎开发环境配置与高效工作流构建实战指南

在游戏开发领域,尤其是使用“996引擎”这类国产游戏引擎进行项目开发时,开发者常常会遇到一系列工程化、效率提升和疑难问题排查的挑战。这些挑战并非源于引擎核心功能的不足,更多是围绕项目配置、资源管理、构建流程、调试效率以及特定环境&…

2026/8/21 11:46:31

188 数码管扫描频率超 60Hz,为什么无关灯管还会随机乱闪?

简介188数码管主要用于显示电量SOC,常用于移动电源领域,显示的状态主要有:充电电量、放电电量、过温爆闪、小电流模式、快充符号及其他定制符号等。188数码管的工作原理是通过主控来控制每个管的开关,电量需要显示的管&#xff0c…

2026/8/20 10:17:13

工业通信系统底层逻辑:04 反射——高频能量撞墙之后会发生什么?

第四篇:反射——高频能量撞墙之后会发生什么? —— 你以为信号已经过去了,其实它正在回来打你 老Q的现场笔记 第五季,我们正式进入工业神经系统层。这里不再是单个设备的战斗,而是整个工厂“经脉”层面的秩序之战。从这一篇开始,你将第一次看清:看似简单的信号传播,背…

2026/8/20 20:11:18

工业传感器与变送器详解:序章 从物理世界到工业数据

序章 从物理世界到工业数据 ——重新认识工业传感器与变送器 工业自动化系统正变得日益复杂。今天的工业现场早已不是简单的控制回路,而是由多层技术共同构成的立体体系:PLC、DCS、SCADA、MES、工业互联网、边缘计算与人工智能。控制系统可以执行复杂算法,工业网络可以实现…

2026/8/21 0:03:13

Linux命令-uucico(UUCP传输程序)

Linux命令-uucico(UUCP传输程序) 🔰简介UUCP 体系简介 📖语法⚙️选项配置文件 💡示例示例 1:基本传输操作示例 2:主模式与从模式示例 3:调试与故障排查示例 4:UUCP 配置…

2026/8/21 0:03:13

Linux命令-uupick(UUCP文件接收工具)

Linux命令-uupick(UUCP文件接收工具)🔰简介uupick 在 UUCP 传输链中的位置📖语法⚙️选项交互命令💡示例示例 1:基本接收操作示例 2:仅处理来自特定系统的文件示例 3:完整 UUCP 文件…

2026/8/20 8:35:23

实测才敢推 AI论文网站 2026最新测评与推荐

2026年真正好用的AI论文网站,核心看生成的论文质量、低AI味、格式正确、学术适配四大指标。综合实测,千笔AI、ThouPen、豆包、DeepSeek、Grammarly 是当前最值得推荐的梯队,覆盖从免费到付费、从中文到英文、从文科到理工的全场景需求。一、综…

2026/8/20 9:15:29

2026必备!AI论文网站测评:最新推荐与深度对比

2026年真正好用的AI论文网站,核心看生成的论文质量、低AI味、格式正确、学术适配四大指标。综合实测,千笔AI、ThouPen、豆包、DeepSeek、Grammarly 是当前最值得推荐的梯队,覆盖从免费到付费、从中文到英文、从文科到理工的全场景需求。 一、…

2026/8/21 0:31:27

摆脱论文困扰!盘点2026年全网爆红的的AI论文写作工具

一天写完毕业论文在2026年已不再是天方夜谭。2026年最炸裂、实测能大幅提速的AI论文写作工具,覆盖选题构思、文献整理、内容生成、格式排版等核心场景,真正帮你高效搞定论文难题。 一、全流程王者:一站式搞定论文全链路(一天定稿首…