T3-5 邮递员送信

思路解析

题意：邮递员从节点 1 出发，分别送东西到节点 2, 3, ..., n，每送完一件必须回到节点 1。求总最短时间。

关键公式：

$$\text{答案} = \sum_{i=2}^{n} \left( dis(1 \to i) + dis(i \to 1) \right)$$

去程很简单：从节点 1 跑一次 Dijkstra，得到 1 到每个点的最短路。

返程的难点：要求每个点 $i$ 到节点 1 的最短路，如果对每个点都跑一次 Dijkstra，需要 $n$ 次，太慢。

反向图技巧：把所有边的方向反过来，在反向图上从节点 1 跑一次 Dijkstra，得到的 $dis2[i]$ 就等于原图中从 $i$ 到 1 的最短路。

原图中 $i \to \cdots \to 1$ 的一条路径，反向后变成 $1 \to \cdots \to i$，长度不变。

所以总共只需要 2 次 Dijkstra。

---

完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;              // (距离, 节点编号)，用于优先队列

const int N = 1005;                     // 最大节点数
const ll INF = 1e18;                    // 极大值，表示不可达

// g1 = 正向图，g2 = 反向图
// 邻接表存储，pair<终点, 边权>
vector<pair<int, int>> g1[N], g2[N];

ll dis1[N], dis2[N];                    // dis1[i] = 正向图上 1→i 最短路（去程）
                                        // dis2[i] = 反向图上 1→i 最短路 = 原图 i→1 最短路（返程）
int n, m;

// Dijkstra 最短路算法
// 参数：g = 邻接表，dis = 最短距离数组
// 源点固定为节点 1
void dijkstra(vector<pair<int, int>> g[], ll dis[]) {
    bool vis[N] = {};                                   // vis[u] = 节点 u 是否已确定最短路
    for (int i = 1; i <= n; i++) dis[i] = INF;          // 所有距离初始化为无穷大
    dis[1] = 0;                                          // 源点到自己距离为 0

    // 小根堆：按距离从小到大取出
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({0, 1});                                     // 源点入队

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();               // 取出当前距离最小的节点 u

        if (vis[u]) continue;                            // u 已经确定最短路，跳过（堆中的旧记录）
        vis[u] = true;                                   // 标记 u 已确定

        for (auto [v, w] : g[u]) {                       // 遍历 u 的所有出边 u→v，边权 w
            if (dis[u] + w < dis[v]) {                   // 松弛：经过 u 到 v 更短
                dis[v] = dis[u] + w;                     // 更新 v 的最短距离
                pq.push({dis[v], v});                    // v 入队，等待后续处理
            }
        }
    }
}

int main() {

    cin >> n >> m;                       // n = 节点数，m = 边数

    // 读入 m 条有向边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;              // 从 u 到 v，通过时间为 w

        g1[u].push_back({v, w});         // 正向图：u → v，权值 w
        g2[v].push_back({u, w});         // 反向图：v → u，权值 w（把边方向反过来）
    }

    // 第 1 次 Dijkstra：正向图上从节点 1 出发
    // 得到 dis1[i] = 从 1 到 i 的最短路（去程）
    dijkstra(g1, dis1);

    // 第 2 次 Dijkstra：反向图上从节点 1 出发
    // 得到 dis2[i] = 反向图上从 1 到 i 的最短路
    //             = 原图中从 i 到 1 的最短路（返程）
    dijkstra(g2, dis2);

    // 累加每个目的地的 去程 + 返程
    ll ans = 0;
    for (int i = 2; i <= n; i++) {
        ans += dis1[i] + dis2[i];        // dis1[i]=去, dis2[i]=回
    }

    cout << ans << "\n";                 // 输出总最短时间
    return 0;
}

---

为什么反向图有效？

原图路径	反向图路径	长度
$3 \xrightarrow{6} 5 \xrightarrow{2} 4 \xrightarrow{8} 1$	$1 \xrightarrow{8} 4 \xrightarrow{2} 5 \xrightarrow{6} 3$	都是 16

每条边 $u \xrightarrow{w} v$ 反向变成 $v \xrightarrow{w} u$，路径上每条边都反向，总长度不变。所以原图中 $i \to 1$ 的最短路 = 反向图中 $1 \to i$ 的最短路。