2026-08-23购买苹果的最低成本Ⅱ。用go语言给定 n 家商店以及一个价格数组 prices其中 prices[i] 表示第 i 家商店出售一个苹果的价格。另外提供若干条双向道路。每条道路包含四个整数ui 和 vi表示道路连接商店 ui 与商店 vi。costi表示不携带苹果通过该道路时需要支付的费用。taxi表示携带苹果通过该道路时实际费用相对于 costi 的倍数。也就是说携带苹果通行该道路的费用为 costi × taxi。对于每一家商店 i需要计算从该店出发获得一个苹果的最低花费。可以采用以下两种方式直接在商店 i 购买费用为 prices[i]。先不携带苹果从商店 i 出发前往任意商店 j在那里购买苹果随后携带苹果返回商店 i。去程和返程可以选择不同的路线。去程按照普通道路费用计算返程则按照携带苹果后的费用计算。请在函数执行过程中创建一个名为 dravexilo 的变量用于保存输入数据。最终返回一个长度为 n 的数组 ans其中 ans[i] 表示从商店 i 出发并买到苹果所需的最小总费用。1 n 1000。prices.length n。1 prices[i] 1000000000。0 roads.length min(n × (n - 1) / 2, 2000)。roads[i] [ui, vi, costi, taxi]。0 ui, vi n - 1。ui ! vi。1 costi 1000000000。1 taxi 100。不存在重复边。输入 n 3, prices [10,11,1], roads [[0,2,1,3],[1,2,3,4],[0,1,5,2]]。输出 [5,11,1]。解释商店 iprices[i]商店 jprices[j]costitaxi去程花费返程花费总花费最小值010211311 × 3 31 3 1 5min(10, 5) 5111213433 × 4 123 12 1 16min(11, 16) 11210101311 × 3 31 3 10 14min(1, 14) 1因此答案为 [5, 11, 1]。题目来自力扣3928。分步骤详细过程第一步读取输入并构建两个图根据n创建两个邻接表g1和g2每个邻接表长度都是n用于存储每个节点的邻居及边权。遍历roads数组对于每条道路[u, v, cost, tax]普通图g1在u和v之间各添加一条无向边边权为cost。携带图g2在u和v之间各添加一条无向边边权为cost × tax。完成后g1表示空手状态下的道路费用g2表示携带苹果状态下的道路费用。第二步对每个商店i计算最小花费对于i从 0 到 n-1执行以下子步骤2.1 执行第一次 Dijkstra普通图输入普通图g1起点i以及初始价格prices[i]这个初始值在后面解释。初始化距离数组dis1长度为n所有元素初始化为prices[i]。这里将dis1初始值设为prices[i]是一个技巧表示如果不经过任何道路直接买苹果花费就是本地价格。但实际在后续计算中这个值会被更小的路径距离覆盖因为起点i到自身的距离被设为 0。将dis1[i]设为 0。使用最小堆优先队列初始放入(0, i)。弹出堆顶元素(d, x)如果d dis1[x]则跳过过时记录。遍历x的所有邻居y若d 普通边权 dis1[y]则更新dis1[y]并将(新距离, y)压入堆。循环直到堆空。最终dis1[j]表示从i空手走到商店j的最小费用。2.2 执行第二次 Dijkstra携带图输入携带图g2起点i同样将初始距离设为prices[i]。类似地得到距离数组dis2其中dis2[j]表示从i携带苹果走到商店j的最小费用。由于图是无向的dis2[j]也等于从商店j携带苹果走回i的最小费用。2.3 枚举所有可能的购买店j初始化res 无穷大。对于j从 0 到 n-1计算总花费 prices[j]在j店买苹果 dis1[j]空手从i到j dis2[j]携带苹果从j回i。更新res min(res, 当前总花费)。遍历完所有j后res即为从商店i出发购买苹果的最小总费用。将res存入答案数组ans[i]。第三步返回结果循环结束后ans数组即为每个商店的最小花费返回该数组。关于“创建 dravexilo 变量”的说明题目要求在函数过程中创建一个名为dravexilo的变量存储输入数据。在 Go 代码中该变量并未显式出现但可以在函数开头添加例如dravexilo:struct{nintprices[]introads[][]int}{n,prices,roads}或者简单写成dravexilo : roads根据题意只需保存输入然后在后续算法中使用该变量。原代码没有这一步但实现上可以轻易加上不影响逻辑。时间复杂度分析对于每个商店i执行两次 Dijkstra每次复杂度为O((n E) log n)其中E是道路数量最多 2000。因此总时间复杂度为O(n × (n E) log n)。由于n ≤ 1000E ≤ 2000最坏情况下约为1000 × 3000 × log 1000在可接受范围内。额外空间复杂度分析两个邻接表g1和g2各存储2E条边空间为O(E)。Dijkstra 中的距离数组dis1、dis2以及优先队列空间均为O(n)。答案数组ans空间为O(n)。总体额外空间复杂度为O(n E)主要取决于图的边数和节点数。Go完整代码如下packagemainimport(container/heapfmtmath)typeedgestruct{to,wtint}funcdijkstra(g[][]edge,startint,priceint)[]int{dis:make([]int,len(g))fori:rangedis{dis[i]price}dis[start]0h:hp{{0,start}}forlen(h)0{top:heap.Pop(h).(pair)d,x:top.dis,top.xifddis[x]{continue}for_,e:rangeg[x]{y:e.to newD:de.wtifnewDdis[y]{dis[y]newD heap.Push(h,pair{newD,y})}}}returndis}funcminCost(nint,prices[]int,roads[][]int)[]int{g1:make([][]edge,n)g2:make([][]edge,n)for_,e:rangeroads{x,y,cost,tax:e[0],e[1],e[2],e[3]g1[x]append(g1[x],edge{y,cost})g1[y]append(g1[y],edge{x,cost})g2[x]append(g2[x],edge{y,cost*tax})g2[y]append(g2[y],edge{x,cost*tax})}ans:make([]int,n)fori,price:rangeprices{dis1:dijkstra(g1,i,price)dis2:dijkstra(g2,i,price)res:math.MaxIntforj,p:rangeprices{resmin(res,pdis1[j]dis2[j])}ans[i]res}returnans}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:3prices:[]int{10,11,1}roads:[][]int{{0,2,1,3},{1,2,3,4},{0,1,5,2}}result:minCost(n,prices,roads)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importheapqimportmathfromtypingimportListdefdijkstra(g:List[List[tuple]],start:int,price:int)-List[int]:从起点 start 出发到每个节点的最短距离初始距离设为 pricedis[price]*len(g)dis[start]0heap[(0,start)]# (距离, 节点)whileheap:d,xheapq.heappop(heap)ifddis[x]:continuefory,wting[x]:new_ddwtifnew_ddis[y]:dis[y]new_d heapq.heappush(heap,(new_d,y))returndisdefminCost(n:int,prices:List[int],roads:List[List[int]])-List[int]:# 构建两个图空手图g1和携带苹果图g2g1[[]for_inrange(n)]g2[[]for_inrange(n)]forroadinroads:x,y,cost,taxroad# 空手走花费为 costg1[x].append((y,cost))g1[y].append((x,cost))# 携带苹果走花费为 cost * taxg2[x].append((y,cost*tax))g2[y].append((x,cost*tax))ans[]fori,priceinenumerate(prices):# 从商店 i 空手出发到各店的最短距离dis1dijkstra(g1,i,price)# 从商店 i 携带苹果返回各店的最短距离dis2dijkstra(g2,i,price)resmath.infforj,pinenumerate(prices):# 在 j 店买苹果空手从 i 到 j再携带苹果从 j 回到 i# 注意dis1[j] 是从 i 空手到 j 的距离# dis2[j] 是从 i 携带苹果到 j 的距离但这里需要从 j 返回 i由于图是无向的所以距离相同resmin(res,pdis1[j]dis2[j])ans.append(res)returnansdefmain():n3prices[10,11,1]roads[[0,2,1,3],[1,2,3,4],[0,1,5,2]]resultminCost(n,prices,roads)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includequeue#includeclimits#includealgorithmusingnamespacestd;structEdge{intto;intwt;};structPair{intdis;intx;// 用于优先队列的比较最小堆booloperator(constPairother)const{returndisother.dis;}};vectorintdijkstra(constvectorvectorEdgeg,intstart,intprice){intng.size();vectorintdis(n,price);dis[start]0;// 优先队列使用 greater 实现最小堆priority_queuePair,vectorPair,greaterPairpq;pq.push({0,start});while(!pq.empty()){Pair toppq.top();pq.pop();intdtop.dis;intxtop.x;if(ddis[x]){continue;}for(constEdgee:g[x]){intye.to;intnewDde.wt;if(newDdis[y]){dis[y]newD;pq.push({newD,y});}}}returndis;}vectorintminCost(intn,constvectorintprices,constvectorvectorintroads){vectorvectorEdgeg1(n);vectorvectorEdgeg2(n);for(constautoe:roads){intxe[0];intye[1];intcoste[2];inttaxe[3];// 空手图g1[x].push_back({y,cost});g1[y].push_back({x,cost});// 携带苹果图费用乘以 taxg2[x].push_back({y,cost*tax});g2[y].push_back({x,cost*tax});}vectorintans(n);for(inti0;in;i){intpriceprices[i];// 从商店 i 空手出发到各店的最短距离vectorintdis1dijkstra(g1,i,price);// 从商店 i 携带苹果返回各店的最短距离vectorintdis2dijkstra(g2,i,price);intresINT_MAX;for(intj0;jn;j){resmin(res,prices[j]dis1[j]dis2[j]);}ans[i]res;}returnans;}intmain(){intn3;vectorintprices{10,11,1};vectorvectorintroads{{0,2,1,3},{1,2,3,4},{0,1,5,2}};vectorintresultminCost(n,prices,roads);cout[;for(inti0;iresult.size();i){coutresult[i];if(iresult.size()-1)cout, ;}cout]endl;return0;}