【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(n\log n)O(nlogn)
- 空间复杂度O ( n ) O(n)O(n)
AC代码
C++
/* * @LastEditTime: 2026-01-27 23:38:15 */classSolution{public:intminCost(intn,vector<vector<int>>&edges){vector<vector<pair<int,int>>>graph(n);// graph[from]: [<to, cost>, ...]for(vector<int>&edge:edges){intfrom=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){returncost;}for(auto[nextTo,nextCost]:graph[to]){nextCost+=cost;if(nextCost>=costs[nextTo]){continue;}costs[nextTo]=nextCost;pq.push({nextCost,nextTo});}}return-1;// FAKE RETURN}};#ifdefined(_WIN32)||defined(__APPLE__)/* 4 [[0,1,3],[3,1,1],[2,3,4],[0,2,2]] */intmain(){intn;string s;while(cin>>n>>s){Solution sol;vector<vector<int>>v=stringToVectorVector(s);cout<<sol.minCost(n,v)<<endl;}return0;}#endif同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
