2026-01-18：边反转的最小路径总成本。用go语言，给定一个包含 n 个点（编号 0 到 n-1）的有向带权图。边集合 edges 中的每一项 edges[i]

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           { returnlen(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)
}

# -*-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)

#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;
    return0;
}