核心思路分层图 Dijkstra将问题拆分为空手前往和携带返程两个状态用分层图统一建模对每个城市单独跑最短路求解。1. 分层设计共 2n 个节点- 层 0下标 0 ~ n-1 空手状态道路边权为原始 cost- 层 1下标 n ~ 2n-1 携带苹果状态道路边权为 cost * tax2. 购买动作建模每个城市 i 增加一条从层 0 到层 1 的有向边权值为 prices[i] 代表在该店购买苹果状态从空手切换为携带。3. 问题转化对每个城市 i 求从层 0 的 i 出发到层 1 的 i 的最短路径即为该城市购买苹果的最低总成本去程空手 → 任意城市购买 → 返程携带。严格匹配签名的 Java 实现javaimport java.util.*;class Solution {public int[] minCost(int n, int[] prices, int[][] roads) {// 构建分层图邻接表0~n-1 空手层n~2n-1 携带层ListListlong[] adj new ArrayList();for (int i 0; i 2 * n; i) {adj.add(new ArrayList());}// 购买苹果的跨层边空手状态i → 携带状态i花费为苹果价格for (int i 0; i n; i) {adj.get(i).add(new long[]{i n, prices[i]});}// 添加双向道路for (int[] road : roads) {int u road[0], v road[1], cost road[2], tax road[3];// 空手层双向边adj.get(u).add(new long[]{v, cost});adj.get(v).add(new long[]{u, cost});// 携带层双向边强转long防止整数溢出long carryCost (long) cost * tax;adj.get(u n).add(new long[]{v n, carryCost});adj.get(v n).add(new long[]{u n, carryCost});}int[] ans new int[n];final long INF Long.MAX_VALUE / 2;// 对每个城市单独执行 Dijkstrafor (int i 0; i n; i) {long[] dist new long[2 * n];Arrays.fill(dist, INF);dist[i] 0;PriorityQueuelong[] pq new PriorityQueue((a, b) - Long.compare(a[0], b[0]));pq.offer(new long[]{0, i});while (!pq.isEmpty()) {long[] curr pq.poll();long d curr[0];int u (int) curr[1];// 第一次到达目标节点即为最短路径提前终止if (u i n) {break;}if (d dist[u]) {continue;}for (long[] edge : adj.get(u)) {int v (int) edge[0];long w edge[1];if (dist[v] d w) {dist[v] d w;pq.offer(new long[]{dist[v], v});}}}ans[i] (int) dist[i n];}return ans;}}复杂度分析- 时间复杂度O(n \cdot m \log n)共执行 n 次堆优化 Dijkstra每次节点数为 2n 总边数约为 2m n 。- 空间复杂度O(n m)存储分层图邻接表与距离数组。关键细节1. 溢出防护 cost * tax 可能超出 int 范围全程用 long 计算路径长度最终强转为 int。2. 提前终止Dijkstra 第一次弹出目标节点层1的i时即可停止显著优化运行效率。3. 本地购买自动覆盖跨层边天然支持在当前城市直接购买的场景无需额外处理。