LeetCode 3650.边反转的最小路径总成本：Dijkstra算法
【LetMeFly】3650.边反转的最小路径总成本：Dijkstra算法
力扣题目链接：https://leetcode.cn/problems/minimum-cost-path-with-edge-reversals/
给你一个包含 n 个节点的有向带权图，节点编号从 0 到 n - 1。同时给你一个数组 edges，其中 edges[i] = [ui, vi, wi] 表示一条从节点 ui 到节点 vi 的有向边，其成本为 wi。
每个节点 ui 都有一个 最多可使用一次 的开关：当你到达 ui 且尚未使用其开关时，你可以对其一条入边 vi → ui 激活开关，将该边反转为 ui → vi 并 立即 穿过它。
反转仅对那一次移动有效，使用反转边的成本为 2 * wi。
返回从节点 0 到达节点 n - 1 的 最小 总成本。如果无法到达，则返回 -1。
示例 1:
输入: n = 4, edges = [[0,1,3],[3,1,1],[2,3,4],[0,2,2]]
输出: 5
解释:
- 使用路径
0 → 1(成本 3)。 - 在节点 1，将原始边
3 → 1反转为1 → 3并穿过它，成本为2 * 1 = 2。 - 总成本为
3 + 2 = 5。
示例 2:
输入: n = 4, edges = [[0,2,1],[2,1,1],[1,3,1],[2,3,3]]
输出: 3
解释:
- 不需要反转。走路径
0 → 2(成本 1)，然后2 → 1(成本 1)，再然后1 → 3(成本 1)。 - 总成本为
1 + 1 + 1 = 3。
提示:
2 <= n <= 5 * 1041 <= edges.length <= 105edges[i] = [ui, vi, wi]0 <= ui, vi <= n - 11 <= wi <= 1000
解题方法：单源最短路的迪杰斯特拉算法
迪杰斯特拉算法的核心是：
每个点只访问一次，每次只访问从起点开始到达后距离最近的点。
每次访问一个点，就把从这个点出发的新的可访问的路径加入优先队列。
讲解在此，视频在此。
- 时间复杂度 O ( n log n ) O(nlog n) O(nlogn)
- 空间复杂度 O ( n ) O(n) O(n)
AC代码
C++
/*
* @LastEditTime: 2026-01-27 23:38:15
*/
class Solution {
public:
int minCost(int n, vector<vector<int>>& edges) {
vector<vector<pair<int, int>>> graph(n); // graph[from]: [, ...]
for (vector<int>& edge: edges) {
int from = edge[0], to = edge[1], cost = edge[2];
graph[from].push_back({to, cost});
graph[to].push_back({from, 2 * cost});
}
vector<int> costs(n, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, 0});
costs[0] = 0;
while (pq.size()) {
auto [cost, to] = pq.top();
pq.pop();
if (cost > costs[to]) {
continue;
}
if (to == n - 1) {
return cost;
}
for (auto[nextTo, nextCost] : graph[to]) {
nextCost += cost;
if (nextCost >= costs[nextTo]) {
continue;
}
costs[nextTo] = nextCost;
pq.push({nextCost, nextTo});
}
}
return -1; // FAKE RETURN
}
};
#if defined(_WIN32) || defined(__APPLE__)
/*
4
[[0,1,3],[3,1,1],[2,3,4],[0,2,2]]
*/
int main() {
int n;
string s;
while (cin >> n >> s) {
Solution sol;
vector<vector<int>> v = stringToVectorVector(s);
cout << sol.minCost(n, v) << endl;
}
return 0;
}
#endif
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
