烟台市网站建设_网站建设公司_Ruby_seo优化

2026-01-18：边反转的最小路径总成本。用go语言，给定一个包含 n 个点（编号 0 到 n-1）的有向带权图。边集合 edges 中的每一项 edges[i] = [ui, vi, wi] 表示从 ui 指向 vi 的有向边，权重为 wi。
每个点都有一次特殊操作的机会：当你到达某个点 u 且还没使用过该点的这次机会时，你可以选择任意一条原本指向 u 的入边 v → u，把它临时改为 u → v 并立即沿着这条新方向移动一次。使用这次临时改向并穿越该边的代价为原边权的两倍（2*wi）。这种改向仅对这次移动生效，之后边的方向恢复且该点的机会就不能再用了。

求从起点 0 到终点 n-1 的最小可能总花费，若无法到达则返回 -1。

2 <= n <= 50000。

1 <= edges.length <= 100000。

edges[i] = [ui, vi, wi]。

0 <= ui, vi <= n - 1。

1 <= wi <= 1000。

输入: 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。

题目来自力扣3650。

算法过程详解

1. 图构建（邻接表）

算法首先将输入的有向图转换为一个无向图的邻接表，但其中蕴含了反转边的规则：

• 对于原始有向图中的每条边u -> v（权重为w），在邻接表中创建两条边：
  • 正常边：从u到v，权重为w。这表示不进行反转，直接沿原方向移动。
  • 反转边：从v到u，权重为2 * w。这表示当位于节点v时，可以使用其特殊操作机会，将一条指向v的入边（即u -> v）反转，并从v移动到u，代价是原权重的两倍 。
• 通过这种方式，节点v的特殊操作机会被隐式地建模为一条从v出发、指向其某个入边起点的、代价加倍的边 。

2. 初始化

• 创建一个距离数组dis，用于记录从起点0到每个节点的当前已知最短距离。初始时，起点0的距离设为0，其他所有节点的距离设为极大值（math.MaxInt）。
• 创建一个最小堆（优先队列）h，用于高效地获取当前未处理节点中距离起点最近的节点。堆中存储的是(distance, node)对。初始时，将起点(0, 0)加入堆中 。

3. Dijkstra算法主循环

算法核心是一个循环，直到堆为空为止：

1. 提取最小节点：从最小堆中弹出当前距离起点最近的节点x及其距离disX。
2. 验证最短路径：检查弹出的disX是否等于dis[x]数组中记录的值。如果disX > dis[x]，说明节点x已经被处理过（有更短的路径先到达了它），当前记录是过时的，直接跳过 。
3. 终止条件：如果当前弹出的节点x就是终点n-1，则立即返回dis[x]作为答案，因为Dijkstra算法保证第一次处理终点时得到的就是最短路径 。
4. 松弛操作：遍历节点x的所有邻居（通过邻接表g[x]）。对于每条从x到y、权重为wt的边：
   • 计算经由x到达y的新距离newDisY = dis[x] + wt。
   • 如果newDisY小于dis[y]的当前值，则找到了一个更短的路径。此时更新dis[y] = newDisY，并将(newDisY, y)这个新的距离估计值加入最小堆中 。

4. 返回结果

• 如果循环结束（堆为空）仍未到达终点n-1，说明终点不可达，返回-1。

算法逻辑与“反转”机会的体现

该算法的巧妙之处在于，它通过图构建阶段的“加边”操作，将节点的“反转”机会直接融入了图的结构中。

• 当算法在计算路径时，如果它选择了一条权重为2*w的“反转边”（从v到u），这在逻辑上就等价于：在到达节点v后，使用了它的特殊操作，反转了边u->v，并立即移动到了u。
• Dijkstra算法会自然地探索所有可能的路径（包含正常边和反转边），并最终找到综合成本最低的路径 。

复杂度分析

时间复杂度：O((V + E) log V)

• V是节点数n，E是原始有向图的边数。在算法构建的邻接表中，边的数量约为2 * E。
• 每个节点最多被从堆中弹出一次，每次弹出后需要遍历其所有出边进行松弛操作。每条边最多被处理一次。
• 最小堆的插入（Push）和删除最小元（Pop）操作的时间复杂度均为 O(log V)。在最坏情况下，每条边都可能引发一次堆操作（插入新距离），因此总的时间复杂度为O((V + E) log V)。

空间复杂度：O(V + E)

• O(V)：用于存储距离数组dis。
• O(E)：用于存储邻接表g。因为每条原始边被表示为两条边，所以邻接表的总空间是 O(E)。
• O(V)：最小堆在最坏情况下可能包含所有节点。
• 因此，总的额外空间复杂度为O(V + E)。

总结

您提供的代码通过扩展图结构来建模节点特有的“边反转”操作，并成功运用了标准的Dijkstra算法和最小堆来高效求解单源最短路径问题。其时间复杂度和空间复杂度在图算法中属于高效范畴，能够处理题目中给出的数据规模（n <= 50000, edges.length <= 100000）。

Go完整代码如下：

packagemainimport("container/heap""fmt""math")funcminCost(nint,edges[][]int)int{typeedgestruct{to,wtint}g:=make([][]edge,n)// 邻接表for_,e:=rangeedges{x,y,wt:=e[0],e[1],e[2]g[x]=append(g[x],edge{y,wt})g[y]=append(g[y],edge{x,wt*2})// 反转边}dis:=make([]int,n)fori:=rangedis{dis[i]=math.MaxInt}dis[0]=0// 起点到自己的距离是 0// 堆中保存 (起点到节点 x 的最短路长度，节点 x)h:=&hp{{}}forh.Len()>0{p:=heap.Pop(h).(pair)disX,x:=p.dis,p.xifdisX>dis[x]{// x 之前出堆过continue}ifx==n-1{// 到达终点returndisX}for_,e:=rangeg[x]{y:=e.to newDisY:=disX+e.wtifnewDisY<dis[y]{dis[y]=newDisY// 更新 x 的邻居的最短路// 懒更新堆：只插入数据，不更新堆中数据// 相同节点可能有多个不同的 newDisY，除了最小的 newDisY，其余值都会触发上面的 continueheap.Push(h,pair{newDisY,y})}}}return-1}typepairstruct{dis,xint}typehp[]pairfunc(h hp)Len()int{returnlen(h)}func(h hp)Less(i,jint)bool{returnh[i].dis<h[j].dis}func(h hp)Swap(i,jint){h[i],h[j]=h[j],h[i]}func(h*hp)Push(v any){*h=append(*h,v.(pair))}func(h*hp)Pop()(v any){a:=*h;*h,v=a[:len(a)-1],a[len(a)-1];return}funcmain(){n:=4edges:=[][]int{{0,2,1},{2,1,1},{1,3,1},{2,3,3}}result:=minCost(n,edges)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-importheapqfromtypingimportListdefminCost(n:int,edges:List[List[int]])->int:# 邻接表g=[[]for_inrange(n)]forx,y,wtinedges:g[x].append((y,wt))# 原边g[y].append((x,wt*2))# 反向边，权重翻倍# 初始化距离数组dist=[float('inf')]*n dist[0]=0# 最小堆，元素为 (起点到节点x的最短距离, 节点x)heap=[(0,0)]# (距离, 节点)whileheap:dis_x,x=heapq.heappop(heap)# 如果当前距离大于已记录的最短距离，跳过ifdis_x>dist[x]:continue# 到达终点ifx==n-1:returndis_x# 遍历邻接节点fory,wting[x]:new_dis_y=dis_x+wtifnew_dis_y<dist[y]:dist[y]=new_dis_y heapq.heappush(heap,(new_dis_y,y))return-1if__name__=="__main__":n=4edges=[[0,2,1],[2,1,1],[1,3,1],[2,3,3]]result=minCost(n,edges)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<queue>#include<climits>#include<functional>usingnamespacestd;intminCost(intn,vector<vector<int>>&edges){// 邻接表：存储 (邻居节点, 权重)vector<vector<pair<int,int>>>g(n);for(constauto&e:edges){intx=e[0],y=e[1],wt=e[2];g[x].emplace_back(y,wt);// 原边g[y].emplace_back(x,wt*2);// 反向边，权重翻倍}// 初始化距离数组vector<int>dist(n,INT_MAX);dist[0]=0;// 最小堆：元素为 (起点到节点x的最短距离, 节点x)// 使用 greater 使 priority_queue 成为最小堆priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;pq.emplace(0,0);// (距离, 节点)while(!pq.empty()){auto[dis_x,x]=pq.top();pq.pop();// 如果当前距离大于已记录的最短距离，跳过if(dis_x>dist[x]){continue;}// 到达终点if(x==n-1){returndis_x;}// 遍历邻接节点for(constauto&[y,wt]:g[x]){intnew_dis_y=dis_x+wt;if(new_dis_y<dist[y]){dist[y]=new_dis_y;pq.emplace(new_dis_y,y);}}}return-1;}intmain(){intn=4;vector<vector<int>>edges={{0,2,1},{2,1,1},{1,3,1},{2,3,3}};intresult=minCost(n,edges);cout<<result<<endl;return0;}