)
3650: 边反转的最小路径总成本
思路：Dijkstra 算法
定义 g[i][j] 表示节点 i 到节点 j 这条边的边权。如果没有 i 到 j 的边，则 g[i][j]=∞。
定义 dis[i] 表示起点 k 到节点 i 的最短路径长度，一开始 dis[k]=0，其余 dis[i]=∞ 表示尚未计算出。
根据 Dijkstra 算法，同一个节点我们只会访问一次，所以「最多可使用一次开关」这个约束是多余的，我们只需把反向边的边权设置为 2wi 即可。答案为 0 到 n−1 的最短路长度。
class Solution { public: int minCost(int n, vector<vector<int>>& edges) { vector<vector<pair<int,int>>> g(n); //邻接表 for(auto& e:edges){ int x=e[0],y=e[1],wt=e[2]; g[x].emplace_back(y,wt); g[y].emplace_back(x,wt*2); } vector<int> dis(n,INT_MAX); //堆中保存 (起点到节点 x 的最短路长度，节点 x) priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq; //小根堆 dis[0]=0; //起点到自己的距离是 0 pq.emplace(0,0); while(!pq.empty()){ auto [dis_x,x]=pq.top(); pq.pop(); if(dis_x>dis[x]) continue; //x之前出堆过 if(x==n-1) return dis_x; //到达终点 for(auto& [y,wt]:g[x]){ auto new_dis_y=dis_x+wt; if(new_dis_y<dis[y]){ dis[y]=new_dis_y; //更新 x 的邻居的最短路 //懒更新堆：只插入数据，不更新堆中数据 //相同节点可能有多个不同的 new_dis_y，除了最小的 new_dis_y，其余值都会触发上面的 continue pq.emplace(new_dis_y,y); } } } return -1; } };
