这道题的本质是多源最短路径问题可以用 Dijkstra 算法 高效解决。思路分析对于每个商店 i答案是在以下两者中取最小值1. 本地购买直接花费 prices[i]。2. 去其他店买空手从 i 到 j 的去程路费 在 j 买苹果的钱 携带苹果从 j 回 i 的返程路费。这里的关键是去程和返程路径可以不同。如果分别计算每个起点复杂度太高。更好的办法是构建两张图· 去程图 (Graph 1)边的权重就是 costi空手。· 返程图 (Graph 2)边的权重是 costi * taxi携带苹果。对于每个起点 i分别在两张图上运行 Dijkstra得到 dist1到各店空手路费和 dist2从各店回来的路费。那么去 j 店买的总成本就是 dist1[j] prices[j] dist2[j]取最小值即可。Python3 代码实现pythonimport heapqfrom typing import Listclass Solution:def minCost(self, n: int, prices: List[int], roads: List[List[int]]) - List[int]:# 构建两张邻接表去程图空手和返程图带苹果g1 [[] for _ in range(n)] # 去程g2 [[] for _ in range(n)] # 返程for u, v, cost, taxi in roads:# 双向道路g1[u].append((v, cost))g1[v].append((u, cost))# 返程权重 cost * taxig2[u].append((v, cost * taxi))g2[v].append((u, cost * taxi))def dijkstra(graph, src):从 src 出发到所有点的最短距离dist [float(inf)] * ndist[src] 0pq [(0, src)]while pq:d, u heapq.heappop(pq)if d dist[u]:continuefor v, w in graph[u]:if dist[v] d w:dist[v] d wheapq.heappush(pq, (dist[v], v))return distans []# 对每个商店作为起点计算for i in range(n):# 去程最短距离空手d1 dijkstra(g1, i)# 返程最短距离带苹果d2 dijkstra(g2, i)best prices[i] # 选项1本地买# 选项2去其他店买for j in range(n):if d1[j] float(inf) and d2[j] float(inf):best min(best, d1[j] prices[j] d2[j])ans.append(best)return ans复杂度分析· 时间复杂度O(n * (n m) log n)对每个起点运行两次 Dijkstra。· 空间复杂度O(n m)用于存储图和距离数组。