恒美微站 Logo 恒美微站
  • 首页
  • 关于我们
  • 建站服务
  • 主题模板
  • 案例展示
  • 资讯中心
  • 联系我们

P1629 邮递员送信【洛谷算法习题】

  • 首页
  • 资讯中心
  • /
  • P1629 邮递员送信【洛谷算法习题】

相关资讯

从 GEM200 升级到 GEM300:老厂改造要补哪几层,为什么没人愿意做? 2026/8/25 13:39:53
数据结构‑二叉树(二):二叉堆从零实现|Heap结构设计 + 建堆优化 + 堆排序深度解析 2026/8/25 13:39:53
Agent系列 2026/8/25 13:39:53

最新资讯

RAG 架构设计 7 个关键决策:从 Chunk 策略到 Reranker 的生产级方案
[FreeRTOS]消息队列(Queue)
Windows系统文件WcnNetsh.dll丢失找不到问题解决
全国GEO服务商怎么选?全域筛选标准与AI搜索落地增长逻辑
Linux驱动-SPI-Linux中通用SPI设备驱动-应用程序调用
2026年5款AI视频总结工具对比:从视频摘要、图文笔记到知识库怎么选?

今日推荐

三步把QQ空间历史说说导出到本地:GetQzonehistory 极简指南
洛谷 P7912:[CSP-J 2021 T4] 小熊的果篮 ← 双向链表
Transformers.js 网页端图像抠图实战:零后端 3 行代码返回透明 PNG

本周热门

Nextcloud 桌面客户端:把同步交给它,你只管改文件
如何将 HTML 转成 Word 文档且格式不丢失?html-to-docx 使用教程
Anki 批量操作卡片完整指南:一次搞定上千张,不再逐张修改

本月精选

如何用DamaiHelper实现演唱会门票的智能自动化抢购:完整技术解决方案指南
第4篇:59 倍性能差距的索引瓶颈定位——一次教科书级的全表扫描调优
终极歌词批量下载神器:5分钟解决离线音乐库歌词同步难题

P1629 邮递员送信【洛谷算法习题】

发布时间:2026/8/25 13:44:53
P1629 邮递员送信【洛谷算法习题】 P1629 邮递员送信网页链接P1629 邮递员送信题目描述有一个邮递员要送东西邮局在节点1 11。他总共要送n − 1 n-1n−1样东西其目的地分别是节点2 22到节点n nn。由于这个城市的交通比较繁忙因此所有的道路都是单行的共有m mm条道路。这个邮递员每次只能带一样东西并且运送每件物品过后必须返回邮局。求送完这n − 1 n-1n−1样东西并且最终回到邮局最少需要的时间。输入格式第一行包括两个整数n nn和m mm表示城市的节点数量和道路数量。第二行到第( m 1 ) (m1)(m1)行每行三个整数u , v , w u,v,wu,v,w表示从u uu到v vv有一条通过时间为w ww的道路。输出格式输出仅一行包含一个整数为最少需要的时间。输入输出样例 #1输入 #15 10 2 3 5 1 5 5 3 5 6 1 2 8 1 3 8 5 3 4 4 1 8 4 5 3 3 5 6 5 4 2输出 #183说明/提示对于30 % 30\%30%的数据1 ≤ n ≤ 200 1 \leq n \leq 2001≤n≤200。对于100 % 100\%100%的数据1 ≤ n ≤ 10 3 1 \leq n \leq 10^31≤n≤1031 ≤ m ≤ 10 5 1 \leq m \leq 10^51≤m≤1051 ≤ u , v ≤ n 1\leq u,v \leq n1≤u,v≤n1 ≤ w ≤ 10 4 1 \leq w \leq 10^41≤w≤104输入保证任意两点都能互相到达。解题思路本题是有向图上的多源多汇最短路求和问题。邮递员每次从邮局1 11出发将物品送到某个节点i ii后返回1 11。总时间等于所有i 2 ∼ n i2\sim ni2∼n的「1 → i 1 \to i1→i的最短路」与「i → 1 i \to 1i→1的最短路」之和。由于道路是有向的去程和返程的最短路可能不同需要分别计算。1. 问题等价转化去程从1 11到每个i ii的最短距离d i s t 1 [ i ] dist1[i]dist1[i]可通过在正向图上运行单源最短路以1 11为源点求得。返程从每个i ii到1 11的最短距离d i s t 2 [ i ] dist2[i]dist2[i]。若在反向图上运行单源最短路以1 11为源点得到的d i s t 2 [ i ] dist2[i]dist2[i]即为原图中i → 1 i \to 1i→1的最短距离。反向图的构造方法将原图中的每条有向边u → v u \to vu→v变为v → u v \to uv→u边权不变。答案∑ i 2 n ( d i s t 1 [ i ] d i s t 2 [ i ] ) \sum_{i2}^n (dist1[i] dist2[i])∑i2n​(dist1[i]dist2[i])。2. 算法实现两次 Dijkstra建图将节点编号扩大为1 ∼ n 1\sim n1∼n和n 1 ∼ 2 n n1\sim 2nn1∼2n两组。对于每条输入边u → v u \to vu→v权值w ww在正向图中添加边u → v u \to vu→v在反向图中添加边v n → u n vn \to unvn→un反向图的节点编号统一加n nn。第一次 Dijkstra以节点1 11为源点在正向图上求最短路径得到d i s t 1 [ i ] d i s [ i ] dist1[i] dis[i]dist1[i]dis[i]i 2 ∼ n i2\sim ni2∼n。第二次 Dijkstra以节点1 n 1n1n为源点在反向图上求最短路径得到d i s t 2 [ i ] d i s [ i n ] dist2[i] dis[in]dist2[i]dis[in]i 2 ∼ n i2\sim ni2∼n对应原节点i ii。累加答案遍历i 2 ∼ n i2\sim ni2∼n将d i s [ i ] dis[i]dis[i]和d i s [ i n ] dis[in]dis[in]相加累加到总答案。输出输出总答案。3. 复杂度分析时间复杂度两次 Dijkstra每次O ( m log ⁡ n ) O(m \log n)O(mlogn)总O ( m log ⁡ n ) O(m \log n)O(mlogn)。n ≤ 10 3 n \le 10^3n≤103m ≤ 10 5 m \le 10^5m≤105完全可行。空间复杂度邻接表存储2 m 2m2m条边距离数组和堆等O ( n m ) O(nm)O(nm)。总结利用反向图计算所有节点到源点的最短路是处理“多对一”最短路的常用技巧。本题只需分别求出1 11到各节点的最短路和各节点到1 11的最短路求和即可。两次 Dijkstra 独立运行代码结构清晰。代码简要说明全局数组与建图head[2n]为链式前向星头指针ver, wei, nxt存储边信息。add(u, v, w)添加一条有向边。读入每条边后正向图添加add(u, v, w)反向图添加add(vn, un, w)。Dijkstra 函数传入源点s初始化距离数组dis为极大值。使用优先队列小根堆按距离贪心松弛。主函数第一次dij(1)累加dis[2..n]到答案。第二次dij(1n)累加dis[n2..2n]到答案。输出答案。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll maxn1234,maxm123456;ll inf9000000000000000LL;ll head[maxn1],ver[maxm1],wei[maxm1],nxt[maxm1],tot,n;voidadd(ll u,ll v,ll w){ver[tot]v;wei[tot]w;nxt[tot]head[u];head[u]tot;}structnodeq{ll x;ll dis;nodeq(ll X,ll DIS):x(X),dis(DIS){}booloperator(constnodeqo)const{returndiso.dis;}};priority_queuenodeq,vectornodeq,greaternodeqpq;ll dis[maxn1];voiddij(ll s){for(ll i1;in1;i)dis[i]inf;dis[s]0;pq.push(nodeq(s,0));while(!pq.empty()){nodeq curpq.top();pq.pop();if(dis[cur.x]cur.dis)continue;for(ll ihead[cur.x];~i;inxt[i]){if(dis[ver[i]]cur.diswei[i]){dis[ver[i]]cur.diswei[i];pq.push(nodeq(ver[i],dis[ver[i]]));}}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);memset(head,-1,sizeof(head));ll m,u,v,w;ll ans0;scanf(%lld%lld,n,m);for(ll i1;im;i){scanf(%lld%lld%lld,u,v,w);add(u,v,w);add(vn,un,w);}dij(1);for(ll i2;in;i)ansdis[i];dij(1n);for(ll i2n;in1;i)ansdis[i];printf(%lld\n,ans);return0;}

关于恒美微站

恒美微站专注于为个体商户、工作室提供极简自助建站服务,让每个人都能轻松拥有专业网站。

快速链接

  • 关于我们
  • 建站服务
  • 主题模板
  • 案例展示
  • 资讯中心

服务项目

  • 可视化建站
  • 拖拽编辑
  • 主题定制
  • SEO 优化
  • 网站托管

联系方式

  • 📍 地址:北京市朝阳区建国路 88 号
  • 📞 电话:400-888-8888
  • ✉️ 邮箱:info@hmyw.cn
  • 🕐 时间:周一至周日 9:00-18:00

© 2024 恒美微站 hmyw.cn 版权所有 | 京 ICP 备 12345678 号