leetcode 2473 购买苹果的最低成本 – 世子之争，素来如此

题目

LeetCode 2473 购买苹果的最低成本：有 n 个城市、若干条双向道路（每条路有一个通行成本）。从城市 i 出发，到某个城市买苹果再返回，购买苹果有成本 appleCost[j]；返程时所有道路成本要乘以因子 k。求从每个城市出发的最小总花费（出发成本 + 买苹果 + 返程成本）。

解题思路

第一步：来回都是最短路

从 A 出发到 B 买苹果再回 A，途中可以多次绕路，但最优方案显然是：去程走最短路，返程走同一条最短路原路返回。因为任何绕路只会让成本更高，而最短路是唯一确定的。

于是从 A 出发的总花费 = dist(A,B) + appleCost[B] + dist(B,A)×k。由于是无向图，dist(A,B) = dist(B,A)，记为 cost，总花费 = cost×(k+1) + appleCost[B]。

第二步：朴素做法与优化

朴素做法：以每个城市为源点跑一次单源最短路，再枚举买苹果的城市 B 取最小值——O(n² log n)，n 大时超时。

关键优化：虚拟源点。新建一个虚拟源点 X，X 到城市 j 连一条权值为 appleCost[j] 的边，同时把所有真实道路权值乘以 (k+1)。那么”从 A 出发买苹果”就等价于：

dist(A, X) = min over B of ( dist(A,B)×(k+1) + appleCost[B] )

这正是我们要求的值！所以只需以 X 为源点跑一次 Dijkstra，得到的 dist[X][j] 反转过来就是”从 j 出发到 X”的最短路——因为边是无向的。复杂度降到 O(n log n)。

实现技巧

不显式建虚拟节点：把所有城市初始距离设为 appleCost[i] 并全部入堆，道路权值乘 (k+1) 后正常跑 Dijkstra——等价于”从 X 出发一步到达所有城市”。

AC 代码（C++17）


class Solution {
public:
    vector<long long> minCost(int n, vector<vector<int>>& roads,
                              vector<int>& appleCost, int k) {
        vector<vector<pair<int,int>>> G(n + 1);
        for (auto& r : roads) {
            int a = r[0], b = r[1];
            long long c = 1LL * r[2] * (k + 1);   // 道路成本整体乘 (k+1)
            G[a].emplace_back(b, c);
            G[b].emplace_back(a, c);
        }

        vector<long long> dist(n + 1, LLONG_MAX);
        vector<int> vis(n + 1, 0);
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;

        // 虚拟源点：一步到达所有城市，代价 = 买苹果成本
        for (int i = 1; i <= n; i++) {
            dist[i] = appleCost[i - 1];
            pq.emplace(dist[i], i);
        }

        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (auto& [v, w] : G[u]) {
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.emplace(dist[v], v);
                }
            }
        }
        dist.erase(dist.begin());   // 去掉 0 号占位
        return dist;
    }
};

复杂度与总结

时间复杂度：O((n + m) log n)，一次 Dijkstra 解决所有起点；
空间复杂度：O(n + m)；
核心套路：“多起点 + 单点汇聚” 或 “单点出发多目标” 类问题，用虚拟源点把多源最短路变成单源最短路，这是图论优化里非常常用的一招（另一个经典例子是超级汇点解决多终点问题）。

题目