---
# System prepended metadata

title: 3650. Minimum Cost Path with Edge Reversals
tags: [leetcode]

---

# 3650. Minimum Cost Path with Edge Reversals
## 演算法
```=
建構有向圖，其中反向邊的權重是 2 * w
使用 Dijkstra's algorithm 找出 0 到 n - 1 的最短路徑
```

## 程式碼
```cpp=
#define oo 1e9
class Solution {
public:
    int minCost(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int,int>>> adj(n);
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            adj[u].push_back({v, w});
            adj[v].push_back({u, 2 * w});
        }

        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        vector<int> dis(n, oo);
        vector<bool> done(n);
        dis[0] = 0;
        pq.push({0, 0});
        while (!pq.empty()) {
            auto [step, u] = pq.top();
            pq.pop();
            if (done[u]) continue;
            done[u] = 1;
            for (auto [v, w] : adj[u]) {
                if (dis[v] > step + w) {
                    dis[v] = step + w;
                    pq.push({dis[v], v});
                }
            }
        }
        return dis[n - 1] == oo ? -1 : dis[n - 1];
    }
};
```