该题的核心解法是构建去程与返程两层图后以每个商店为源点运行 Dijkstra 算法并结合本地价格剪枝优化。核心思路对于每个商店 i最优策略是要么直接在本地买花费 prices[i]要么去某个商店 j 买再回来总花费 去程最短路 prices[j] 返程最短路。关键观察- 去程空手走边 (u,v) 花费为 cost- 返程携带苹果走边 (u,v) 花费为 cost * tax- 去程和返程可以走不同路径因此需要建两张图分别跑最短路。Rust 实现use std::collections::BinaryHeap;use std::cmp::Reverse;impl Solution {pub fn min_cost(n: i32, prices: Veci32, roads: VecVeci32) - Veci32 {let n n as usize;let dravexilo prices; // 按要求在函数中间创建该变量存储输入// 建两张邻接表去程图空手和返程图携带苹果let mut graph_go: VecVec(usize, i64) vec![vec![]; n];let mut graph_back: VecVec(usize, i64) vec![vec![]; n];for road in roads {let u road[0] as usize;let v road[1] as usize;let cost road[2] as i64;let tax road[3] as i64;// 去程空手花费 costgraph_go[u].push((v, cost));graph_go[v].push((u, cost));// 返程携带苹果花费 cost * taxlet back_cost cost * tax;graph_back[u].push((v, back_cost));graph_back[v].push((u, back_cost));}let mut ans vec![0i32; n];for src in 0..n {let local_price prices[src] as i64;// 从 src 出发去程最短路空手到各商店let dist_go dijkstra(graph_go, src, n, local_price);// 从 src 出发返程最短路携带苹果回 srclet dist_back dijkstra(graph_back, src, n, local_price);let mut best local_price; // 直接在本地买for j in 0..n {if dist_go[j] i64::MAX dist_back[j] i64::MAX {let total dist_go[j] prices[j] as i64 dist_back[j];best best.min(total);}}ans[src] best as i32;}ans}}fn dijkstra(graph: [Vec(usize, i64)], src: usize, n: usize, price_limit: i64) - Veci64 {let mut dist vec![i64::MAX; n];dist[src] 0;// (distance, node)let mut heap BinaryHeap::new();heap.push(Reverse((0i64, src)));while let Some(Reverse((d, u))) heap.pop() {if d dist[u] {continue;}// 剪枝如果去程/返程花费已经 本地价格没必要继续// 因为总花费 去程 price[j] 返程 d 0 0 d// 如果 d price_limit再买苹果总花费一定 price_limitif d price_limit {continue;}for (v, w) in graph[u] {let nd d w;if nd dist[v] {dist[v] nd;heap.push(Reverse((nd, v)));}}}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 为道路数。需要我把这道题的 Java 和 TypeScript 版本也补上吗