LeetCode每日一题：3650. 边反转的最小路径总成本

题目描述

给定一个包含 n 个节点的有向带权图，节点编号从 0 到 n - 1。同时给定一个数组 edges，其中 edges[i] = [ui, vi, wi] 表示一条从节点 ui 到节点 vi 的有向边，其成本为 wi。每个节点 ui 都有一个最多可使用一次的开关：当你到达 ui 时，可以选择反转一条从 ui 出发的边，反转后该边的成本变为原来的两倍。现在要求你计算从节点 0 到节点 n-1 的最小路径总成本。

解题思路

这个问题可以转化为在图中寻找一条从节点 0 到节点 n-1 的最短路径，其中每条边可以选择是否反转，反转后成本增加一倍。为了简化问题，我们可以将每条边都视为双向边，即将每条边都加入图中两次，一次是正向，一次是反向，反向的边成本增加一倍。这样，我们就可以使用 Dijkstra 算法来求解最短路径问题。

代码实现

下面是使用堆优化的 Dijkstra 算法求解该问题的代码实现：

class Solution {
public:
    int minCost(int n, vector<vector<int>>& edges) {
        // 构建邻接表
        vector<vector<pair<int, int>>> adjList(n);
        for (auto& e : edges) {
            adjList[e[0]].emplace_back(make_pair(e[1], e[2]));
            adjList[e[1]].emplace_back(make_pair(e[0], e[2] * 2));
        }
        
        // Dijkstra 算法
        vector<int> costs(n, INT_MAX);
        vector<bool> visited(n, false);
        priority_queue<Node, vector<Node>, greater<Node>> pq;
        pq.emplace(Node{0, 0});
        costs[0] = 0;
        
        while (!pq.empty()) {
            Node curr = pq.top();
            pq.pop();
            
            if (visited[curr.idx]) continue;
            visited[curr.idx] = true;
            
            if (curr.idx == n - 1) return curr.cost;
            
            for (auto& p : adjList[curr.idx]) {
                if (visited[p.first]) continue;
                int newCost = curr.cost + p.second;
                if (newCost < costs[p.first]) {
                    costs[p.first] = newCost;
                    pq.emplace(Node{p.first, newCost});
                }
            }
        }
        
        return -1;
    }
};

struct Node {
    int idx;
    int cost;
    
    bool operator>(const Node& node) const {
        return cost > node.cost;
    }
};

总结

通过将每条边都视为双向边，并使用 Dijkstra 算法，我们可以有效地求解边反转的最小路径总成本问题。这种方法的关键在于将问题转化为标准的最短路径问题，并利用 Dijkstra 算法的效率来求解。

注意事项

在处理大规模图时，应该使用邻接表来存储图，而不是邻接矩阵，以优化空间和时间的效率。

LeetCode每日一题：3650. 边反转的最小路径总成本