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

发布时间:2026/8/25 13:45:11

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;}

相关新闻

PHP报名系统源码一出,人工报名直接变废纸

PHP报名系统源码一出,人工报名直接变废纸

2026/8/25 13:45:11

“基于 PHP - Mysql 框架的网络报名系统开发”, 这个资源所描述的是一个借助 PHP MySQL 框架搭建而成的网络报名系统, 它主要是用来处理等级考试(就像计算机等级考试那样)的在线报名流程的, 该系统的目的在于解决传统人工报名方式所带来的工作量巨大、容…

CIMPro孪大师|公共交通枢纽大客流全景数字孪生管理方案

CIMPro孪大师|公共交通枢纽大客流全景数字孪生管理方案

2026/8/25 13:45:11

1 行业现状痛点日均客流量巨大,高峰管控压力大;站体空间复杂,治安管控难以全覆盖;单点智能化已有建设,但跨系统融合应用不足;干扰因素多,单一环节故障就会传导扩散;多部门协同&#…

【2015-02-23】Linux常用命令备份:ar

【2015-02-23】Linux常用命令备份:ar

2026/8/25 13:45:11

[历史归档] 本文原发布于 cstriker1407.info 个人博客,内容为历史存档,仅供参考。 发布时间: 2015-02-23 | 标题:Linux常用命令备份:ar | 分类: 编程 / linux | 标…

Nature子刊 IF=15.1 | AI辅助ICD编码的真实世界部署与评估:基于大模型与临床文档标准化

Nature子刊 IF=15.1 | AI辅助ICD编码的真实世界部署与评估:基于大模型与临床文档标准化

2026/8/25 14:25:19

引言 国际疾病分类(ICD)编码是医院运营的基石,但手动编码过程耗时费力且易出错,已成为全球医疗机构的沉重负担。尽管人工智能(AI)技术为自动化编码带来了希望,但现有模型往往难以适应真实世界中…

全局快门 vs 滚动快门:工业读码器选型必看参数

全局快门 vs 滚动快门:工业读码器选型必看参数

2026/8/25 14:25:19

工业读码器的快门类型,指的是图像传感器曝光时的工作方式,主要分为全局快门(Global Shutter)和滚动快门(Rolling Shutter)两种。这个参数直接决定了读码器能不能拍清楚高速运动的条码,是工业读码…

Kimi    LeetCode LCP 27. 黑盒光线反射 Python3实现

Kimi LeetCode LCP 27. 黑盒光线反射 Python3实现

2026/8/25 14:25:19

这是 LeetCode LCP 27. 黑盒光线反射 的 Python3 实现。解题思路核心思想是预处理所有光线循环 有序集合维护:1. 状态定义:每个状态由 (小孔序号, 方向) 组成。方向 1 表示沿 yx,-1 表示沿 y-x。 2. 预处理循环:利用数学公式直接…

Linux学习21-hadoop续及hadoop高可用部署

Linux学习21-hadoop续及hadoop高可用部署

2026/8/25 14:25:19

yarn部署新增节点node4下载nfs执行yum install nfs-utils命令下载安装NFS相关工具包。node1做免密,与本机也做免密在node1上生成SSH密钥对,并将公钥分发到各节点,实现免密登录。将node1的公钥添加到本机authorized_keys中,实现本机…

驾校管理系统源码 Java+SpringBoot+Vue 万字文档 前后分离

驾校管理系统源码 Java+SpringBoot+Vue 万字文档 前后分离

2026/8/25 14:25:19

一、关键词驾校管理系统,驾校一体化管理平台,驾培机构信息化管理系统二、作品包含源码数据库万字设计文档全套环境和工具资源本地部署教程三、项目技术前端技术:Html、Css、Js、Vue2、Element-ui后端技术:Java、SpringBoot2、MyBa…

面向具身智能的TVA-VLA价值对齐与安全约束机制

面向具身智能的TVA-VLA价值对齐与安全约束机制

2026/8/25 14:15:17

前沿技术探索:TVA智能体(简称TVA)TVA智能体(亦称“AI智能体视觉”或“TVA视觉智能体”)是依托Transformer架构与“因式智能体”理论构建的系统级视觉技术框架。它融合深度强化学习(DRL)、卷积神…

[光学原理与应用-521]:对光的错误理解与纠偏

[光学原理与应用-521]:对光的错误理解与纠偏

2026/8/24 19:53:32

首先光是一种能量的载体和形态,宏观上观察到的光是由无数个微观的光量子组成的,每个光子在产生的瞬间,其在真空的空间中以确定不变的速度沿着一个初始的方向一直向前,在微观层面,每个光量子的运动轨迹是以波函数所展现…

SIP通话转接原理与REFER方法实战解析

SIP通话转接原理与REFER方法实战解析

2026/8/24 19:56:07

1. 通话转接不是“挂断再拨号”,而是SIP会话的动态重定向你有没有遇到过这样的场景:客服坐席A正在和客户通电话,突然需要把这通对话无缝转给专家坐席B,客户完全感知不到中间的断连——既没听到忙音,也没被要求重新拨号…

Kolla-ansible单节点OpenStack部署实战:从环境准备到排坑指南

Kolla-ansible单节点OpenStack部署实战:从环境准备到排坑指南

2026/8/24 21:16:09

1. 为什么选择Kolla-ansible来部署单节点OpenStack?如果你正在寻找一种能把OpenStack从“概念”快速变成“可用的实验环境”的方法,那么Kolla-ansible几乎是当前最主流、最省心的选择。我见过太多人卡在手动编译依赖、配置服务、处理版本冲突的泥潭里&am…

三步把QQ空间历史说说导出到本地:GetQzonehistory 极简指南

三步把QQ空间历史说说导出到本地:GetQzonehistory 极简指南

2026/8/25 0:04:34

三步把QQ空间历史说说导出到本地:GetQzonehistory 极简指南 【免费下载链接】GetQzonehistory 获取QQ空间发布的历史说说 项目地址: https://gitcode.com/GitHub_Trending/ge/GetQzonehistory Meta Description:GetQzonehistory 是一个QQ空间历史说…

洛谷 P7912:[CSP-J 2021 T4] 小熊的果篮 ← 双向链表

洛谷 P7912:[CSP-J 2021 T4] 小熊的果篮 ← 双向链表

2026/8/25 0:04:35

【题目来源】 https://www.luogu.com.cn/problem/P7912 【题目描述】 小熊的水果店里摆放着一排 n 个水果。每个水果只可能是苹果或桔子,从左到右依次用正整数 1,2,…,n 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里&#x…

Transformers.js 网页端图像抠图实战:零后端 3 行代码返回透明 PNG

Transformers.js 网页端图像抠图实战:零后端 3 行代码返回透明 PNG

2026/8/25 0:04:35

Transformers.js 网页端图像抠图实战:零后端 3 行代码返回透明 PNG 【免费下载链接】transformers.js State-of-the-art Machine Learning for the web. Run 🤗 Transformers directly in your browser, with no need for a server! 项目地址: https:/…

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

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

2026/8/22 2:02:26

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

导师推荐!2026最新AI论文工具测评与实用推荐

导师推荐!2026最新AI论文工具测评与实用推荐

2026/8/22 4:13:47

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

告别游戏崩溃:XCOM 2模组管理器的智能革命

告别游戏崩溃:XCOM 2模组管理器的智能革命

2026/8/22 1:32:34

告别游戏崩溃:XCOM 2模组管理器的智能革命 【免费下载链接】xcom2-launcher The Alternative Mod Launcher (AML) is a replacement for the default game launchers from XCOM 2 and XCOM Chimera Squad. 项目地址: https://gitcode.com/gh_mirrors/xc/xcom2-lau…