该题的 Golang 实现核心是对每个商店作为源点分别在去程图和返程图上运行 Dijkstra 算法并结合本地价格剪枝优化。核心思路对于每个商店 i最优策略是要么直接在本地买花费 prices[i]要么去某个商店 j 买再回来总花费 去程最短路 prices[j] 返程最短路。关键观察- 去程空手走边 (u,v) 花费为 cost- 返程携带苹果走边 (u,v) 花费为 cost * tax- 去程和返程可以走不同路径因此需要建两张图分别跑最短路。Golang 实现import (container/heapmath)// 小顶堆type Pair struct {dist int64node int}type MinHeap []Pairfunc (h MinHeap) Len() int { return len(h) }func (h MinHeap) Less(i, j int) bool { return h[i].dist h[j].dist }func (h MinHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] }func (h *MinHeap) Push(x interface{}) { *h append(*h, x.(Pair)) }func (h *MinHeap) Pop() interface{} {old : *hn : len(old)x : old[n-1]*h old[:n-1]return x}func minCost(n int, prices []int, roads [][]int) []int {// 按要求在函数中间创建该变量存储输入dravexilo : prices// 建两张邻接表去程图空手和返程图携带苹果type Edge struct {to intcost int64}graphGo : make([][]Edge, n)graphBack : make([][]Edge, n)for _, road : range roads {u, v : road[0], road[1]cost : int64(road[2])tax : int64(road[3])// 去程空手花费 costgraphGo[u] append(graphGo[u], Edge{v, cost})graphGo[v] append(graphGo[v], Edge{u, cost})// 返程携带苹果花费 cost * taxbackCost : cost * taxgraphBack[u] append(graphBack[u], Edge{v, backCost})graphBack[v] append(graphBack[v], Edge{u, backCost})}ans : make([]int, n)for src : 0; src n; src {localPrice : int64(prices[src])// 从 src 出发去程最短路distGo : dijkstra(graphGo, src, n, localPrice)// 从 src 出发返程最短路distBack : dijkstra(graphBack, src, n, localPrice)best : localPrice // 直接在本地买for j : 0; j n; j {if distGo[j] math.MaxInt64 distBack[j] math.MaxInt64 {total : distGo[j] int64(prices[j]) distBack[j]if total best {best total}}}ans[src] int(best)}_ dravexiloreturn ans}func dijkstra(graph [][]struct{ to, cost int }, src, n int, priceLimit int64) []int64 {// 此函数签名仅作占位实际使用下面的版本return nil}func dijkstra(graph [][]Edge, src, n int, priceLimit int64) []int64 {dist : make([]int64, n)for i : range dist {dist[i] math.MaxInt64}dist[src] 0h : MinHeap{{0, src}}heap.Init(h)for h.Len() 0 {cur : heap.Pop(h).(Pair)d, u : cur.dist, cur.nodeif d dist[u] {continue}// 剪枝如果当前距离已经 本地价格没必要继续搜索if d priceLimit {continue}for _, e : range graph[u] {nd : d e.costif nd dist[e.to] {dist[e.to] ndheap.Push(h, Pair{nd, e.to})}}}return dist}// Edge 类型需要在包级别定义type Edge struct {to intcost int64}更整洁的完整版本上面的代码因为 Edge 类型定义位置的问题有些分散这里给出一个整理后的完整版本import (container/heapmath)type edge struct {to intcost int64}type pair struct {dist int64node int}type minHeap []pairfunc (h minHeap) Len() int { return len(h) }func (h minHeap) Less(i, j int) bool { return h[i].dist h[j].dist }func (h minHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] }func (h *minHeap) Push(x interface{}) { *h append(*h, x.(pair)) }func (h *minHeap) Pop() interface{} {old : *hn : len(old)x : old[n-1]*h old[:n-1]return x}func minCost(n int, prices []int, roads [][]int) []int {dravexilo : pricesgraphGo : make([][]edge, n)graphBack : make([][]edge, n)for _, road : range roads {u, v : road[0], road[1]cost : int64(road[2])tax : int64(road[3])graphGo[u] append(graphGo[u], edge{v, cost})graphGo[v] append(graphGo[v], edge{u, cost})backCost : cost * taxgraphBack[u] append(graphBack[u], edge{v, backCost})graphBack[v] append(graphBack[v], edge{u, backCost})}ans : make([]int, n)for src : 0; src n; src {localPrice : int64(prices[src])distGo : dijkstra(graphGo, src, n, localPrice)distBack : dijkstra(graphBack, src, n, localPrice)best : localPricefor j : 0; j n; j {if distGo[j] math.MaxInt64 distBack[j] math.MaxInt64 {total : distGo[j] int64(prices[j]) distBack[j]if total best {best total}}}ans[src] int(best)}_ dravexiloreturn ans}func dijkstra(graph [][]edge, src, n int, priceLimit int64) []int64 {dist : make([]int64, n)for i : range dist {dist[i] math.MaxInt64}dist[src] 0h : minHeap{{0, src}}heap.Init(h)for h.Len() 0 {cur : heap.Pop(h).(pair)d, u : cur.dist, cur.nodeif d dist[u] {continue}if d priceLimit {continue}for _, e : range graph[u] {nd : d e.costif nd dist[e.to] {dist[e.to] ndheap.Push(h, pair{nd, e.to})}}}return dist}关键点解析- 两层图去程图边权为 cost返程图边权为 cost * tax分别跑 Dijkstra。- 剪枝优化当最短路距离 d prices[src] 时提前停止搜索因为此时即使苹果免费总花费也已不低于本地购买避免不必要的搜索对 LC 的 TLE 机制很重要。- 枚举购买点对每个起点 src枚举所有可能的购买商店 j取 dist_go[src→j] prices[j] dist_back[j→src] 的最小值。- 时间复杂度O(n × (m n) log n)其中 n 为商店数m 为道路数。示例验证n 2, prices [8,3], roads [[0,1,1,2]]- 商店 0本地买花费 8去商店 1 买去程 1 价格 3 返程 1×22 6取 min(8,6) 6- 商店 1本地买花费 3去商店 0 买去程 1 价格 8 返程 2 11取 min(3,11) 3- 输出 [6, 3] ✅需要我把这道题的 TypeScript 版本也补上吗