3650. 邊反轉的最小路徑總成本

思路

反轉邊的成本是原先成本的兩倍，將這個條件加入之後，套用 Dijkstra 演算法即可。 每個節點只會被訪問一次，因此題目的限制相當於沒有。

程式碼

Dijkstra

class Solution
{
public:
    int minCost(int n, vector<vector<int>>& edges)
    {
        vector<vector<pair<int, int>>> graph(n);
        for(auto edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].push_back({v, w});
            // 反轉邊
            graph[v].push_back({u, 2 * w});
        }

        // 初始化距離為最大值        
        // dist[u] = 到 u 的當前最短路徑
        vector<int> dist(n, INT_MAX);
        dist[0] = 0;

        // 成本, 節點
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // 根據成本排序。
        pq.push({0, 0});

        while(!pq.empty()) {
            auto [cost, u] = pq.top();
            pq.pop();
            // 如果當前成本比較大，那沒希望了。
            if(cost > dist[u])
                continue;
            // 看看所有鄰居，延伸
            for(auto& [v, w] : graph[u]) {
                if(dist[v] > cost + w) {  // 之前到鄰居的成本 > 來到當前節點，再花費 w 的成本，就表示現在的選擇比較好。
                    dist[v] = cost + w;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist[n - 1] == INT_MAX ? -1 : dist[n - 1];
    }
};

複雜度分析

• 時間複雜度：$O(n + m\log{m})$
• 空間複雜度：$O(n + m)$