2026-01-18：边反转的最小路径总成本。用go语言，给定一个包含 n 个点（编号 0 到 n-1）的有向带权图。边集合 edges 中的每一项 edges[i] = [ui, vi, 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算法主循环

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

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完整代码如下：

package main

import (
"container/heap"
"fmt"
"math"
)

func minCost(n int, edges [][]int) int {
type edge struct{ to, wt int }
g := make([][]edge, n) // 邻接表
for _, e := range edges {
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)
for i := range dis {
dis[i] = math.MaxInt
}
dis[0] = 0 // 起点到自己的距离是 0
// 堆中保存 (起点到节点 x 的最短路长度，节点 x)
h := &hp{{}}

for h.Len() > 0 {
p := heap.Pop(h).(pair)
disX, x := p.dis, p.x
if disX > dis[x] { // x 之前出堆过
continue
}
if x == n–1 { // 到达终点
return disX
}
for _, e := range g[x] {
y := e.to
newDisY := disX + e.wt
if newDisY < dis[y] {
dis[y] = newDisY // 更新 x 的邻居的最短路
// 懒更新堆：只插入数据，不更新堆中数据
// 相同节点可能有多个不同的 newDisY，除了最小的 newDisY，其余值都会触发上面的 continue
heap.Push(h, pair{newDisY, y})
}
}
}

return –1
}

type pair struct{ dis, x int }
type hp []pair

func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int) { 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 }

func main() {
n := 4
edges := [][]int{{0, 2, 1}, {2, 1, 1}, {1, 3, 1}, {2, 3, 3}}
result := minCost(n, edges)
fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import heapq
from typing import List

def minCost(n: int, edges: List[List[int]]) –> int:
# 邻接表
g = [[] for _ in range(n)]
for x, y, wt in edges:
g[x].append((y, wt)) # 原边
g[y].append((x, wt * 2)) # 反向边，权重翻倍

# 初始化距离数组
dist = [float('inf')] * n
dist[0] = 0

# 最小堆，元素为 (起点到节点x的最短距离, 节点x)
heap = [(0, 0)] # (距离, 节点)

while heap:
dis_x, x = heapq.heappop(heap)

# 如果当前距离大于已记录的最短距离，跳过
if dis_x > dist[x]:
continue

# 到达终点
if x == n – 1:
return dis_x

# 遍历邻接节点
for y, wt in g[x]:
new_dis_y = dis_x + wt
if new_dis_y < dist[y]:
dist[y] = new_dis_y
heapq.heappush(heap, (new_dis_y, y))

return –1

if __name__ == "__main__":
n = 4
edges = [[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>

using namespace std;

int minCost(int n, vector<vector<int>>& edges) {
// 邻接表：存储 (邻居节点, 权重)
vector<vector<pair<int, int>>> g(n);
for (const 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> 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) {
return dis_x;
}

// 遍历邻接节点
for (const auto& [y, wt] : g[x]) {
int new_dis_y = dis_x + wt;
if (new_dis_y < dist[y]) {
dist[y] = new_dis_y;
pq.emplace(new_dis_y, y);
}
}
}

return –1;
}

int main() {
int n = 4;
vector<vector<int>> edges = {{0, 2, 1}, {2, 1, 1}, {1, 3, 1}, {2, 3, 3}};
int result = minCost(n, edges);
cout << result << endl;
return 0;
}