2477.到达首都的最少油耗

链接：2477.到达首都的最少油耗
难度：Medium
标签：树、深度优先搜索、广度优先搜索、图
简介：请你返回到达首都最少需要多少升汽油。

题解 1 - cpp

• 编辑时间：2022-11-20
• 执行用时：796ms
• 内存消耗：256.5MB
• 编程语言：cpp
• 解法介绍：递归，从外向里遍历。

// bestlyg
# define X first
# define Y second
# define lb(x) ((x) & (-x))
# define mem(a,b) memset(a,b,sizeof(a))
# define debug freopen("r.txt","r",stdin)
# define pi pair<int,int>
#ifdef DEBUG
#define log(frm, args...) {    printf(frm, ##args);}
#else
#define log(frm, args...)
#endif
typedef long long ll;
using namespace std;
struct City {
    int len, idx, size;
    unordered_set<int> next;
    City(): len(0), idx(0), size(1) {}
};
class Solution {
public:
    vector<City> list;
    vector<int> idxlist;
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        if (n == 1) return 0;
        list = vector<City>(n);
        idxlist = vector<int>(n);
        for (int i = 0; i < n; i++) {
            list[i].idx = i;
            idxlist[i] = i;
        }
        for (auto &road : roads) {
            list[road[0]].next.insert(road[1]);
            list[road[1]].next.insert(road[0]);
        }
        initLen();
        // for (int i = 0; i < n; i++) {
        //     cout << "i = " << i
        //          << ", len = " << list[i].len
        //          << ", idx = " << list[i].idx
        //          << ", next = ";
        //     for (auto &next : list[i].next) {
        //         cout << next << ", ";
        //     }
        //     cout << endl;
        // }
        sort(idxlist.begin(), idxlist.end(), [&](auto &a, auto &b){
            return list[a].len < list[b].len;
        });
        // cout << "-====" << endl;
        long long ans = 0;
        for (int idx = n - 1; idx > 0; idx--) {
            int i = idxlist[idx];
            ans += 1 + (list[i].size - 1) / seats;
            int next = *list[i].next.begin();
            list[next].size += list[i].size;
            list[next].next.erase(i);
            // cout << "i = " << i
            //      << ", idx = " << list[i].idx
            //      << ", next = " << list[next].idx
            //      << ", cursize = " << list[i].size
            //      << ", nextsize = " << list[next].size
            //      << endl;
        }
        return ans;
    }
    void initLen() {
        queue<int> q;
        q.push(0);
        int size = 1, cur = 1;
        while (q.size()) {
            int node = q.front();
            q.pop();
            for (auto &next : list[node].next) {
                if (next == 0 || list[next].len != 0) continue;
                list[next].len = cur;
                q.push(next);
            }
            if (--size == 0) {
                size = q.size();
                cur++;
            }
        }
    }
};

题解 2 - python

• 编辑时间：2023-12-05
• 执行用时：352ms
• 内存消耗：52.7MB
• 编程语言：python
• 解法介绍：贪心，每次批量运送。

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        n = len(roads) + 1
        counts = [1] * n
        nodes = [[] for _ in range(n)]
        for n1, n2 in roads:
            nodes[n1].append(n2)
            nodes[n2].append(n1)
        q = deque()
        for i in range(1, n):
            if len(nodes[i]) == 1:
                q.append(i)
        ans = 0
        while q:
            idx = q.popleft()
            if len(nodes[idx]) == 1:
                ans += ceil(counts[idx] / seats)
                next_idx = nodes[idx][0]
                nodes[next_idx].remove(idx)
                counts[next_idx] += counts[idx]
                if next_idx != 0 and len(nodes[next_idx]) == 1:
                    q.append(next_idx)
        return ans