Problem: 100684. 边反转的最小路径总成本

[TOC]

思路

最短路

题目说 最多可使用一次，其实使用无限次也不会改变答案，因为边权是正数，同一个点走多一次，结果成本只会越高，所以可以直接无视这个条件，跑一遍最短路即可：

建图

反向权重要翻倍

        road = defaultdict(list)
        for x,y,w in edges:
            road[x].append((y,w))
            road[y].append((x,2*w))©leetcode

dijkstra

        heap = [(0,0)]
        tgt = n - 1
        dist = [inf] * n
        dist[0] = 0
        while heap:
            t,node = heappop(heap)
            if dist[node] < t:
                continue

            if node == tgt:
                return t

            for nxt,w in road[node]:
                nt = t + w
                if dist[nxt] > nt:
                    dist[nxt] = nt
                    heappush(heap,(nt,nxt))©leetcode

更多题目模板总结，请参考2024年度总结与题目分享

Code

###Python3

class Solution:
    def minCost(self, n: int, edges: List[List[int]]) -> int:
        '''
        实际反转无限次都可以，成本只会越来越大
        '''
        road = defaultdict(list)
        for x,y,w in edges:
            road[x].append((y,w))
            road[y].append((x,2*w))

        heap = [(0,0)]
        tgt = n - 1
        dist = [inf] * n
        dist[0] = 0
        while heap:
            t,node = heappop(heap)
            if dist[node] < t:
                continue

            if node == tgt:
                return t

            for nxt,w in road[node]:
                nt = t + w
                if dist[nxt] > nt:
                    dist[nxt] = nt
                    heappush(heap,(nt,nxt))

        return -1