题解 | #邮递员送信#

问题建模

该问题本质上是一个在一个具有 $n$ 个节点和 $m$ 条边的有向带权图（Directed Weighted Graph）中，计算单源最短路径（Single Source Shortest Path, SSSP）与其逆问题的组合。

题目要求分别计算 $1 \to i$ 的最短路径和 $i \to 1$ 的最短路径，并求其总和。

即求解目标为：

$\text{Total Cost} = \sum_{i=2}^{n} (dist(1, i) + dist(i, 1))$

其中 $dist(u, v)$ 表示节点 $u$ 到 $v$ 的最短路径耗时。
约束分析
- 规模约束： $N \le 1000$ , $M \le 10^5$ 。虽然 $N$ 较小，但 $M$ 较大。
- 权重约束： $w_i > 0$ （非负权边），这为选择 Dijkstra 算法提供了理论基础，避免了 Bellman-Ford 或 SPFA 在负权情况下的性能开销。
- 复杂度陷阱：
  - 如果是无向图， $dist(1, i) = dist(i, 1)$ ，只需计算一次。但本题为单向图，往返路径不同。
  - 直接对每个节点 $i$ ( $2 \sim n$ ) 分别运行一次最短路算法来计算 $dist(i, 1)$ 会导致调用 $n$ 次算法，产生巨大的冗余计算。

核心算法

为了满足性能要求并保持代码的清晰，采用 两次 Dijkstra + 反向图（Transpose Graph） 的策略。

1. 算法范式选择：Dijkstra (堆优化版)

选择理由：由于边权均为正数，Dijkstra 是求解单源最短路径的最优选择。
数据结构：使用 二叉堆（优先队列） 优化，能够在处理稠密图或稀疏图时保持稳定的对数级性能。

2. “多源归一”问题的转化：反向图技术

求解 $\sum dist(1, i)$ 是标准的单源最短路径问题，运行一次 Dijkstra 即可。难点在于求解 $\sum dist(i, 1)$ （多源汇聚到一点）。

常规思路缺陷：若对每个起点 $i$ 运行 Dijkstra，总时间复杂度为 $O(n \cdot m \log n)$ 。在本题数据规模下约为 $10^3 \times 10^5 \times 10 \approx 10^9$ 次运算，这会超时（通常限制 $10^8$ 指令/秒）。
优化策略：利用图的转置性质。在原图 $G$ 中， $i \to 1$ 的最短路径，等价于在反向图 $G_{rev}$ （将所有边方向取反，权重不变）中 $1 \to i$ 的最短路径。即： $dist_G(i, 1) \equiv dist_{G_{rev}}(1, i)$ 。

结论：通过构建反向图，我们将“多源到单点”的问题转化为“单点到多源”的问题。只需在 $G$ 和 $G_{rev}$ 上各运行一次 Dijkstra，共两次即可解决问题。

代码实现

#include <bits/stdc++.h>
#include <limits>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

static constexpr int INF = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<pii>> adj(n + 1);
    vector<vector<pii>> rev_adj(n + 1);
    for (int i = 0; i < m; i++) {
        int  u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        rev_adj[v].push_back({u, w});
    }

    auto dijkstra = [](int start, int n, const vector<vector<pii>>& adj,
    vector<int>& dist) {
        dist.assign(n + 1, INF);
        vector<bool> visited(n + 1, false);

        priority_queue<pii, vector<pii>, greater<pii>> pq;
        dist[start] = 0;
        pq.push({0, start});

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();

            if (visited[u])
                continue;
            visited[u] = true;

            for (const auto&[v, w] : adj[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
    };

    vector<int> dist;
    dijkstra(1, n, adj, dist);

    vector<int> rev_dist;
    dijkstra(1, n, rev_adj, rev_dist);

    ll total = 0LL;
    for (int i = 2; i <= n; i++) {
        total += (ll)dist[i] + (ll)rev_dist[i];
    }

    cout << total << endl;
}

复杂度分析

1. 时间复杂度

Dijkstra (堆优化)：单次运行的复杂度为 $O(m \log n)$ 。
总复杂度：我们需要运行两次 Dijkstra，加上线性扫描求和。 $T(n, m) = 2 \times O(m \log n) + O(n) \approx O(m \log n)$
代入规模： $m=10^5, n=10^3$ 。 $\log n \approx 10$ 。计算量约为 $2 \times 10^6$ 次操作，这远低于 $10^8$ 的常规时限，属于极优解。
对比 Floyd-Warshall：Floyd 算法可以求出任意两点间距离，但复杂度为 $O(n^3) \approx 10^9$ ，在本题中极大概率超时。

2. 空间复杂度

邻接表存储：需要存储原图和反向图，每条边存储两次。 $S(n, m) = O(n + m)$
辅助空间：距离数组 dist 和优先队列均占用 $O(n)$ 或 $O(m)$ 。
总空间： $O(n + m)$ ，内存占用极低，完全符合要求。

3. 其他算法讨论

SPFA 算法：若使用 SPFA (Queue-optimized Bellman-Ford)，平均复杂度为 $O(k \cdot m)$ (k常数较小)。但在特意构造的网格图或稠密图中，SPFA 会退化为 $O(n \cdot m)$ 。鉴于本题保证非负权，Dijkstra 是最稳定且无风险的选择。
稠密图优化：如果 $m$ 接近 $n^2$ (即 $m \approx 10^6$ )，使用朴素版 Dijkstra (无堆优化，每次线性扫描找最小值) 复杂度为 $O(n^2)$ ，可能比 $O(m \log n)$ 略优。但本题 $m=10^5$ 远小于 $n^2=10^6$ ，稀疏图特性明显，堆优化版本更佳。

总结

该问题的最优解法是：基于邻接表的双向图构建 + 两次堆优化 Dijkstra。通过反向图技巧处理回程路径，将原本潜在的 $O(n \cdot m \log n)$ 复杂度降维至 $O(m \log n)$ 。