最小体力消耗路径 -- dijkstra算法应用

1631. 最小体力消耗路径
这道题和标准dijkstra算法的区别：
标准dijkstra算法，判断⼀条路径是⻓还是短的标准是路径经过的权重总和，而该题是路径经过的权重最⼤值，因此权重计算的方法要转换下，来到当前点的体力消耗和从当前点到下一个邻居节点的体力消耗，取两者的最大值。

class Solution:
    class State:
        def __init__(self, x, y, distFromStart):
            """
            从start节点到当前节点的距离
            :param id:
            :param distFromStart:
            """
            self.x = x
            self.y = y
            self.distFromStart = distFromStart

        def __lt__(self, other):
            if self.distFromStart < other.distFromStart:
                return True
            return False

    def adj(self, matrix, x, y):
        m = len(matrix)
        n = len(matrix[0])
        neighbors = []
        # 定义上下左右四个行走方向
        # 四个方向的顺序无关紧要
        directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        for dir in directs:
            nx = x + dir[0]
            ny = y + dir[1]
            # 越界
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            neighbors.append([nx, ny])

        return neighbors

    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m = len(heights)
        n = len(heights[0])
        # dp table，distTo[i]可理解为节点s到节点i的最短路劲，后续要不停地更新该表
        effortTo = [[float('inf') for _ in range(n)] for _ in range(m)]
        # base case
        effortTo[0][0] = 0

        min_heap = []
        # 从起点s开始BFS
        heapq.heappush(min_heap, self.State(0, 0, 0))

        while min_heap:
            curState = heapq.heappop(min_heap)
            curNode_x = curState.x
            curNode_y = curState.y
            curDistFromStart = curState.distFromStart

            # 如果只关心start 节点到某一个终点end的最短距离，此处加入一个判断即可
            if curNode_x == m-1 and curNode_y == n-1:
                return curDistFromStart

            if curDistFromStart > effortTo[curNode_x][curNode_y]:
                # 已经有一条更短的路径到达curNode节点了
                continue

            # 遍历curNodeID的相邻节点
            for neighbor in self.adj(heights, curNode_x, curNode_y):
                next_x = neighbor[0]
                next_y = neighbor[1]

                #  计算从 (curX, curY) 达到 (nextX, nextY) 的消耗
                effortToNextNode = max(effortTo[curNode_x][curNode_y],
                                       abs(heights[curNode_x][curNode_y] - heights[next_x][next_y]))

                if effortToNextNode < effortTo[next_x][next_y]:
                    # 更新dp table
                    effortTo[next_x][next_y] = effortToNextNode
                    # 将该邻居节点加入优先级队列
                    heapq.heappush(min_heap, self.State(next_x, next_y, effortToNextNode))

        return -1
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78