2477. 到达首都的最少油耗

2477. 到达首都的最少油耗

• 难度: medium
• 原始链接: https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital
• 标签: 贪心, 深度优先遍历

解法一: 深度优先遍历

go

func minimumFuelCost(roads [][]int, seats int) int64 {
    n := len(roads)
    trees := make([][]int, n + 1)
    for _, road := range roads {
        trees[road[0]] = append(trees[road[0]], road[1])
        trees[road[1]] = append(trees[road[1]], road[0])
    }
    var ans int64 = 0
    var dfs func (son, parent int) int
    dfs = func (son, parent int) int {
        count := 0
        for _, tree := range trees[son] {
            if tree != parent {
                curCount := dfs(tree, son) + 1
                count += curCount
                ans += int64((curCount + seats - 1) / seats)
            }
        }
        return count
    }
    dfs(0, -1)
    return ans
}