购买苹果的最低成本

2473. 购买苹果的最低成本

给你一个正整数 n，表示从 1 到 n 的 n 个城市。还给你一个二维数组 roads，其中 roads[i] = [a_i, b_i, cost_i] 表示在城市 a_i 和 b_i 之间有一条双向道路，其旅行成本等于 cost_i。

你可以在任何城市买到苹果，但是有些城市买苹果的费用不同。给定数组 appleCost ，其中 appleCost[i] 是从城市 i 购买一个苹果的成本。

你从某个城市开始，穿越各种道路，最终从 任何一个 城市买一个苹果。在你买了那个苹果之后，你必须回到你 开始的 城市，但现在所有道路的成本将乘以一个给定的因子 k。

给定整数 k，返回一个大小为 n 的数组 answer，其中 answer[i] 是从城市 i 开始购买一个苹果的最小总成本。

示例 1:

输入: n = 4, roads = [[1,2,4],[2,3,2],[2,4,5],[3,4,1],[1,3,4]], appleCost = [56,42,102,301], k = 2
输出: [54,42,48,51]
解释: 每个起始城市的最低费用如下:
- 从城市 1 开始:你走路径 1 -> 2，在城市 2 买一个苹果，最后走路径 2 -> 1。总成本是 4 + 42 + 4 * 2 = 54。
- 从城市 2 开始:你直接在城市 2 买一个苹果。总费用是 42。
- 从城市 3 开始:你走路径 3 -> 2，在城市 2 买一个苹果，最后走路径 2 -> 3。总成本是 2 + 42 + 2 * 2 = 48。
- 从城市 4 开始:你走路径 4 -> 3 -> 2，然后你在城市 2 购买，最后走路径 2 -> 3 -> 4。总成本是 1 + 2 + 42 + 1 * 2 + 2 * 2 = 51。

示例 2:

输入: n = 3, roads = [[1,2,5],[2,3,1],[3,1,2]], appleCost = [2,3,1], k = 3
输出: [2,3,1]
解释: 在起始城市买苹果总是最优的。

提示:

2 <= n <= 1000
1 <= roads.length <= 1000
1 <= a_i, b_i <= n
a_i != b_i
1 <= cost_i <= 10⁵
appleCost.length == n
1 <= appleCost[i] <= 10⁵
1 <= k <= 100
没有重复的边。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<long long> minCost(int n, vector<vector<int>>& roads, vector<int>& appleCost, int k) { } };

java 解法, 执行用时: 2117 ms, 内存消耗: 43.7 MB, 提交时间: 2023-10-22 10:46:28

class Solution {
    class Test{
        Integer nextRoad;
        Integer cost;
        Test(int nextRoad,int cost){
            this.nextRoad = nextRoad;
            this.cost = cost;
        }
    }

    class Road{
        Integer road;
        Integer cost;
        List<Integer> list = new ArrayList<>();
        Road(int road,int cost){
            this.road = road;
            this.cost = cost;
        }
    }
    public long[] minCost(int n, int[][] roads, int[] appleCost, int k) {

        Map<Integer,List<Test>> map = new HashMap<>();
        for(int [] road : roads){
            if(map.containsKey(road[0])){
                Test test = new Test(road[1],road[2]);
                map.get(road[0]).add(test);
            }else {
                List<Test> tests = new ArrayList<>();
                tests.add(new Test(road[1],road[2]));
                map.put(road[0],tests);
            }
            if(map.containsKey(road[1])){
                Test test = new Test(road[0],road[2]);
                map.get(road[1]).add(test);
            }else {
                List<Test> tests = new ArrayList<>();
                tests.add(new Test(road[0],road[2]));
                map.put(road[1],tests);
            }
        }

        long[] ret = new long[n];
        for(int i = 1; i <= n ; i ++){
            int min = appleCost[i - 1];
            Deque<Road> roadsDeque = new LinkedList<>();
            Road road1 = new Road(i,0);
            road1.list.add(i);
            roadsDeque.add(road1);
            while (!roadsDeque.isEmpty()){
                Road road =  roadsDeque.pollFirst();
                List<Test> tests = map.get(road.road);
                if(tests == null)
                    break;
                for(Test test : tests){
                    int next = test.nextRoad;
                    int cost = test.cost;
                    if(road.list.contains(next) || road.cost > min)
                        continue;
                    int temp = appleCost[next - 1] + cost + k*cost + road.cost;
                    min = Math.min(temp,min);
                    Road road2 = new Road(next,cost+ k*cost + road.cost);
                    road2.list.addAll(road.list);
                    road2.list.add(next);
                    roadsDeque.add(road2);
                }
            }

            ret[i - 1] = min;
        }
        //广度优先遍历

        return  ret;

    }
}

python3 解法, 执行用时: 1096 ms, 内存消耗: 17 MB, 提交时间: 2023-10-22 10:45:57

class Solution:
    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:
        g = defaultdict(list)
        for a, b, cost in roads:
            g[a - 1].append([b - 1, cost])
            g[b - 1].append([a - 1, cost])
        
        def dijkstra(start: int):
            ans = float('inf')
            dist = [float('inf')] * n
            dist[start] = 0
            q = [(0, start)]
            while q:
                cost, x = heapq.heappop(q)
                ans = min(ans, cost * (k + 1) + appleCost[x])
                if dist[x] < cost:
                    continue
                for y, cost in g[x]:
                    d = dist[x] + cost
                    if d < dist[y]:
                        dist[y] = d
                        heapq.heappush(q, (d, y))
            return ans
        
        ans = [0] * n
        for i in range(n):
            ans[i] = dijkstra(i)
        return ans

python3 解法, 执行用时: 56 ms, 内存消耗: 17 MB, 提交时间: 2023-10-22 10:45:39

class Solution:
    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:
        g = collections.defaultdict(list)
        for a, b, c in roads:
            g[a - 1].append((b - 1, c * (k + 1)))
            g[b - 1].append((a - 1, c * (k + 1)))
        visit = [0] * n
        pq = sorted((c, i) for i, c in enumerate(appleCost))
        while pq:
            c, u = heapq.heappop(pq)
            if visit[u]:
                continue
            visit[u] = 1
            for v, nc in g[u]:
                if appleCost[v] > c + nc:
                    appleCost[v] = c + nc
                    heapq.heappush(pq, (appleCost[v], v))
        return appleCost

cpp 解法, 执行用时: 12 ms, 内存消耗: 11.7 MB, 提交时间: 2023-10-22 10:45:24

typedef pair<int, int> PII;

const int N = 1010;
bool st[N];
int e[N << 1], w[N << 1], ne[N << 1], h[N], idx;


void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}


class Solution {
public:
    vector<long long> minCost(int n, vector<vector<int>>& roads, vector<int>& appleCost, int k) {
        memset(st, false, sizeof(st));
        memset(h, -1, sizeof(h)), idx = 0;
        for (auto& road : roads) {
            int a = road[0] - 1, b = road[1] - 1, c = road[2];
            add(a, b, c * (k + 1)), add(b, a, c * (k + 1));
        }
        priority_queue<PII, vector<PII>, greater<PII>> pq;
        for (int i = 0; i < n; ++i) pq.emplace(appleCost[i], i);
        while (!pq.empty()) {
            auto [c, u] = pq.top();
            pq.pop();
            if (st[u]) continue;
            st[u] = true;
            for (int i = h[u]; ~i; i = ne[i]) {
                int v = e[i];
                if (appleCost[v] > c + w[i]) {
                    appleCost[v] = c + w[i];
                    pq.emplace(appleCost[v], v);
                }
            }
        }
        return vector<long long>(appleCost.begin(), appleCost.end());
    }
};

上一题

下一题

详情