P1629 邮递员送信
题目描述
有一个邮递员要送东西，邮局在节点 \(1\)。他总共要送 \(n-1\) 样东西，其目的地分别是节点 \(2\) 到节点 \(n\)。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 \(m\) 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 \(n-1\) 样东西并且最终回到邮局最少需要的时间。
输入格式
第一行包括两个整数，\(n\) 和 \(m\)，表示城市的节点数量和道路数量。
第二行到第 \((m+1)\) 行，每行三个整数，\(u,v,w\)，表示从 \(u\) 到 \(v\) 有一条通过时间为 \(w\) 的道路。
输出格式
输出仅一行，包含一个整数，为最少需要的时间。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
对于 \(30\%\) 的数据，\(1 \leq n \leq 200\)。
对于 \(100\%\) 的数据，\(1 \leq n \leq 10^3\)，\(1 \leq m \leq 10^5\)，\(1\leq u,v \leq n\)，\(1 \leq w \leq 10^4\)，输入保证任意两点都能互相到达。
Tip
📌 题目分析
给定数据： * 节点数 \(n \le 1000\)，有向边数 \(m \le 10^5\)。 * 邮局在节点 \(1\)，每次送货的过程是：\(1 \to i\)，然后 \(i \to 1\)。 * 求跑完所有节点 \(2\) 到 \(n\) 的总时间。
👉 本质： 求中心点到其他所有点的最短路，以及其他所有点回到中心点的最短路。
👉 类型： 单源最短路径（Dijkstra） + 反向建图神技。
🧠 解题思路
1️⃣ 问题拆解
邮递员送一件物品的总距离可以分为两段： 1. 去程（\(1 \to i\)）：这非常简单，就是以节点 \(1\) 为起点，跑一次标准的单源最短路算法（如 Dijkstra）。 2. 回程（\(i \to 1\)）：这是一个“多源单汇”问题（从多个起点出发，到一个固定的终点）。
2️⃣ 为什么需要“反向建图”？
如果按常规思路处理回程，我们需要以每个节点 \(i\) 为起点，分别跑一次 Dijkstra 去寻找回到节点 \(1\) 的路径。这样总共需要跑 \(N\) 次 Dijkstra，时间复杂度会达到 \(O(N \times M \log N)\)，面对这道题极大概率会超时（TLE）。
神仙操作来了：反向建图 既然所有的边都是单行道（有向边），我们不妨把所有边的方向全部反转，建立一个“镜像平行世界”（反向图）。 * 在原图中，从 \(i\) 走到 \(1\) 的路径。 * 在反向图中，就等价于从 \(1\) 走到 \(i\) 的路径！
这意味着，我们只需要在反向图上，以节点 \(1\) 为起点，再跑一次 Dijkstra，就能以 \(O(M \log N)\) 的超快速度，一次性求出所有点回到节点 \(1\) 的最短距离！
3️⃣ 时间与空间复杂度
- 空间： 开两个邻接表，分别存正向图和反向图，空间复杂度 \(O(N + M)\)。
- 时间： 跑两次堆优化 Dijkstra，时间复杂度 \(O(M \log N)\)。 完全降维打击，极速秒杀。
💻 C++代码
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
// 定义无穷大（表示初始不可达）
const int INF = 0x3f3f3f3f;
// 最大点数（题目 n <= 1000）
const int N = 1005;
int n, m;
// 原图：存 u -> v 的边
vector<pair<int,int>> g[N];
// 反图：存 v -> u 的边
vector<pair<int,int>> rg[N];
// dis1[i] = 邮局1到i的最短路
// dis2[i] = i回邮局1的最短路（通过反图求）
int dis1[N], dis2[N];
// Dijkstra 最短路
// adj[] 表示图
// dis[] 用来存结果
void dijkstra(vector<pair<int,int>> adj[], int dis[])
{
// 小根堆：{当前最短距离, 点编号}
priority_queue<
pair<int,int>,
vector<pair<int,int>>,
greater<pair<int,int>>
> pq;
// 标记数组：该点是否已确定最短路
bool vis[N] = {0};
// 初始化距离为无穷大
for(int i = 1; i <= n; i++)
dis[i] = INF;
// 起点是邮局1号点
dis[1] = 0;
pq.push({0,1});
while(!pq.empty())
{
// 取出当前距离最小的点
int u = pq.top().second;
pq.pop();
// 已处理过则跳过
if(vis[u]) continue;
// 标记已确定最短路
vis[u] = 1;
// 遍历u的所有邻边
for(auto e : adj[u])
{
int v = e.first; // 终点
int w = e.second; // 边权
// 松弛操作：若经过u到v更短
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
pq.push({dis[v], v});
}
}
}
}
int main()
{
cin >> n >> m;
// 输入m条边
for(int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v,w}); // 原图：u -> v
rg[v].push_back({u,w}); // 反图：v -> u
}
// 第一次：求1到所有点最短路
dijkstra(g, dis1);
// 第二次：求所有点回1最短路
// 在反图中，相当于1到所有点
dijkstra(rg, dis2);
int ans = 0;
// 节点2到n都要送一次并回来
for(int i = 2; i <= n; i++)
{
ans += dis1[i] + dis2[i];
}
cout << ans;
return 0;
}
⚠️ 易错点
❌ 1. 结果累加导致整数溢出 (WA)
单个路径的最长距离大约是 \(N \times W = 1000 \times 10000 = 10^7\)，用 int 存 dist 是安全的。
但是！ 总和要把去程和回程近 2000 条路的距离全加起来，最大可能达到 \(2 \times 10^{10}\)。而 C++ 中 32 位 int 的极限只有 \(2 \times 10^9\)。如果 total_time 不开 long long，累加到最后直接变成负数，满盘皆输。
❌ 2. 误判为无向图
很多刚学图论的同学做送货/旅游题，习惯性地建立双向边 adj[u].push_back(v) 和 adj[v].push_back(u)。
题目中明确说了“所有的道路都是单行的”，如果在原图里建了双向边，去程和回程就混杂在一起了，不仅逻辑全错，连反向建图的精髓也用不上了。
❌ 3. Dijkstra 跑 \(N\) 遍
正如思路里提到的，如果你在原图上用循环跑 \(N\) 遍 Dijkstra 来求 \(i \to 1\)，虽然逻辑没毛病，但在 \(M=10^5\) 的数据下绝对会超时。一定要时刻警惕这种不必要的重复计算。