首页 > 试题广场 >

邮递员送信

[编程题]邮递员送信

热度指数：922 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 某城市共有 $n$ 个路口与 $m$ 条单向道路（交通繁忙，均为单行道）。其中 $1$ 号路口为邮局， $2 \sim n$ 号路口各有一件包裹待投递。

$\hspace{15pt}$ 邮递员一次只能携带一件包裹，每次从邮局取件后出发，沿道路送达对应目的地后 必须返回邮局 才能取下一件。求完成所有 $n-1$ 件投递并最终回到邮局所需的 最短总时间。

输入描述:

第一行输入两个整数  —— 路口数量与道路数量。 
接下来  行，每行输入三个整数 ，表示一条从  单向通往  的道路，耗时为 。 
保证任意两点间 互相可达。

输出描述:

输出一个整数，代表完成全部投递并返回邮局的最少总时间。

示例1

输入

输出

算法知识视频讲解

kilomatutinal

发表于 2026-01-23 11:25:25

这道题好难，首先要知道Dijkstra算法喵~其实就是最短路径算法喵~Dijkstra算法的核心思想：贪心+广度优先搜索想象一下，猫猫（起点）在一个有很多房间（顶点）和走廊（边）的大房子里，每个走廊的长度（权重）都不一样。猫猫想知道自己去每个房间的最短路径，特别是去那个藏着小鱼干的房间（终点）的最短展开全文

丨阿伟丨

发表于 2025-09-09 16:09:00

题目链接邮递员送信题目描述在一个有个路口和条单向道路的城市里，1 号路口是邮局。邮递员需要向 2 号到号路口的每一个路口都投递一件包裹。投递规则如下：邮递员一次只能携带一件包裹。每次都必须从 1 号路口（邮局）出发，前往目的地路口。送达后，必须返回 1 号路口（邮局），才展开全文

yunayu

发表于 2026-01-23 01:00:34

本题题意是对于每一个点i，向结果累加1->i与i->1的最短路长度。我们知道朴素版Dijkstra可以在O(n^2)的复杂度内处理出单个点到全图的单源最短路。最最朴素的思想是对于每一个点，都去求出其到其余所有点的最短路，但是这样时间复杂度来到了O(n^3)。注意到i->1的最短路等展开全文

_changbin

发表于 2026-01-23 01:57:52

单元最短路 Dijkstra算法解决，数据范围较小，朴素版即可解决O(n²）（因为我只会朴素版） #include<bits/stdc++.h> #include <vector> using namespace std; #define int long long cons 展开全文

BeauWill

发表于 2026-01-23 02:38:21

由于邮递员只能一封一封地送信，为了使总时间最少，每次应该走最短路到达各个路口，然后从各个路口返回时也应走最短路回到邮局。但是由于道路是单向的，因此邮递员出发的时候是单源最短路，可以用堆优化版dijkstra算法计算最短路，而回来的时候是多源最短路，但我们可以反向思考，若建立的是反图，邮递员回邮局的路展开全文

蚂蚁🐜a

发表于 2026-01-23 13:14:57

#include<bits/stdc++.h> #include <cstring> using namespace std; #define int long long #define x first #define y second #define space ' ' 展开全文

微风只想睡觉

发表于 2026-01-24 01:34:04

#include <climits> #include<iostream> #include<vector> #include<array> #include<algorithm> #include<functional> #i 展开全文

bandiaoz

发表于 2025-08-08 21:10:16

题目链接邮递员送信题目描述有个路口与条单向道路（均为单行道），号路口为邮局，号路口各有一件包裹待投递。邮递员一次只能携带一件包裹，每次需从邮局取件出发，将包裹送达目的地后必须返回邮局，方可取下一件。已知任意两点间互相可达，求完成全部件投递并最终回到邮局所需的最短总时间。解展开全文

Turgen

发表于 2026-01-23 01:37:45

我们希望1到X和X到1都是最短路，有个难点是多个起点到终点的最短路，就要用到反向建边，反向建一个图，然后跑1到x的最短路，得到的结果就是x到1的最短路，因为这条路径是反着的，我们扭回来就正好是x到1了。在形式上不要写的像我一样，可以用vector模拟静态邻接链表。时间复杂度O(mlogn) #inc 展开全文