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

解题思路
从A点出发，到B点买苹果，然后回到A点，要求找到最小花费。先不考虑买完苹果之后的成本要乘上因子K这一限制，然后贪心地考虑一下，A->B 和 B->A 来回都选择最短路才是最优的，而最短路的花费是唯一确定的，所以来回的花费是一样的，那么总花费是2倍的最短路。此时再考虑因子K，买完苹果之后，因子K对所有路径生效，所以虽然最短路变贵了，但其它的路只会更贵，最短路还是“那条路径”，因子K并不影响“该怎么走”，只是路费要整个乘上k。假设A->B 最短路的花费是 cost,那么 B->A 按照最短路原路返回，花费为 cost * k ,那么来回的总花费为 cost * (k+1).

以A为源点，求解单源最短路，然后枚举B点（也就是买苹果的点），min(dist(A,B)+appleCost(B) ) 即为anser[A] ,但题目要求所有的anser，那么还需要枚举A点作为源点，依次求解anser[A]。时间复杂度为 (n² log ⁿ) .

考虑优化一下，建立一个虚拟源点 X，X与任意城市之间都有一条路，花费为在目标城市买苹果的成本。那么题意就可以转化一下，变成求从源点X开始，到任意城市的最短路（乘上(k+1)）。此时只需要用Dijkstra求解一次即可，时间复杂度为 N*log^N 。
————————————————

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 &road:roads){
            int &a=road[0],&b=road[1],cost=road[2]*(k+1);
            G[a].emplace_back(b,cost);
            G[b].emplace_back(a,cost);
        }
        vector<long long>dis(n+1);
        vector<int>vis(n+1);
        auto cmp=[](pair<int,int>&a,pair<int,int>&b){
            return a.second>b.second;
        };
        priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)>q(cmp);
        for(int i=1;i<=n;i++){
            dis[i]=appleCost[i-1];
            q.emplace(i,dis[i]);
        }
        while(!q.empty()){
            int u=q.top().first;
            q.pop();
            if(vis[u])continue;
            vis[u]=true;
            for(auto &[v,cost]:G[u]){
                if(dis[v]>dis[u]+cost){
                    dis[v]=dis[u]+cost;
                    q.emplace(v,dis[v]);
                }
            }
        } 
        dis.erase(dis.begin());
        return dis;
    }
};

相关文章