企业官网建设流程全解析

西安网站优化服务,微商城开发用华网天下首选,郑州网站+建设,wordpress百度主动插件2026-01-18#xff1a;边反转的最小路径总成本。用go语言#xff0c;给定一个包含 n 个点#xff08;编号 0 到 n-1#xff09;的有向带权图。边集合 edges 中的每一项 edges[i] [ui, vi, wi] 表示从 ui 指向 vi 的有向边#xff0c;权重为 wi。 每个点都有一次特殊操作的…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算法主循环算法核心是一个循环直到堆为空为止提取最小节点从最小堆中弹出当前距离起点最近的节点x及其距离disX。验证最短路径检查弹出的disX是否等于dis[x]数组中记录的值。如果disX dis[x]说明节点x已经被处理过有更短的路径先到达了它当前记录是过时的直接跳过 。终止条件如果当前弹出的节点x就是终点n-1则立即返回dis[x]作为答案因为Dijkstra算法保证第一次处理终点时得到的就是最短路径 。松弛操作遍历节点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是节点数nE是原始有向图的边数。在算法构建的邻接表中边的数量约为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/heapfmtmath)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.xifdisXdis[x]{// x 之前出堆过continue}ifxn-1{// 到达终点returndisX}for_,e:rangeg[x]{y:e.to newDisY:disXe.wtifnewDisYdis[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].dish[j].dis}func(h hp)Swap(i,jint){h[i],h[j]h[j],h[i]}func(h*hp)Push(v any){*happend(*h,v.(pair))}func(h*hp)Pop()(v any){a:*h;*h,va[: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,xheapq.heappop(heap)# 如果当前距离大于已记录的最短距离跳过ifdis_xdist[x]:continue# 到达终点ifxn-1:returndis_x# 遍历邻接节点fory,wting[x]:new_dis_ydis_xwtifnew_dis_ydist[y]:dist[y]new_dis_y heapq.heappush(heap,(new_dis_y,y))return-1if__name____main__:n4edges[[0,2,1],[2,1,1],[1,3,1],[2,3,3]]resultminCost(n,edges)print(result)C完整代码如下#includeiostream#includevector#includequeue#includeclimits#includefunctionalusingnamespacestd;intminCost(intn,vectorvectorintedges){// 邻接表存储 (邻居节点, 权重)vectorvectorpairint,intg(n);for(constautoe:edges){intxe[0],ye[1],wte[2];g[x].emplace_back(y,wt);// 原边g[y].emplace_back(x,wt*2);// 反向边权重翻倍}// 初始化距离数组vectorintdist(n,INT_MAX);dist[0]0;// 最小堆元素为 (起点到节点x的最短距离, 节点x)// 使用 greater 使 priority_queue 成为最小堆priority_queuepairint,int,vectorpairint,int,greaterpairint,intpq;pq.emplace(0,0);// (距离, 节点)while(!pq.empty()){auto[dis_x,x]pq.top();pq.pop();// 如果当前距离大于已记录的最短距离跳过if(dis_xdist[x]){continue;}// 到达终点if(xn-1){returndis_x;}// 遍历邻接节点for(constauto[y,wt]:g[x]){intnew_dis_ydis_xwt;if(new_dis_ydist[y]){dist[y]new_dis_y;pq.emplace(new_dis_y,y);}}}return-1;}intmain(){intn4;vectorvectorintedges{{0,2,1},{2,1,1},{1,3,1},{2,3,3}};intresultminCost(n,edges);coutresultendl;return0;}