1345. 跳跃游戏 IV

import heapq
from collections import defaultdict


def dijkstra(edges, f, t):
    g = defaultdict(list)
    for l, r, c in edges:
        g[l].append((c, r))

    # dist records the min value of each node in heap.
    q, seen, dist = [(0, f)], set(), {f: 0}
    while len(q) > 0:
        cost, v1 = heapq.heappop(q)
        if v1 in seen:
            continue

        seen.add(v1)
        if v1 == t:
            return cost

        for c, v2 in g.get(v1, ()):
            if v2 in seen:
                continue
            # Not every edge will be calculated. Edges which can improve the value of node in heap will be useful.
            if v2 not in dist or cost + c < dist[v2]:
                dist[v2] = cost + c
                heapq.heappush(q, (cost + c, v2))
    return float("inf")

import heapq
from collections import defaultdict
from typing import List


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        keymap = defaultdict(list)
        for i, a in enumerate(arr):
            keymap[a].append(i)

        visited, q = {0}, []
        heapq.heappush(q, (0, 0))
        while len(q) > 0:
            step, idx = heapq.heappop(q)
            if idx == len(arr) - 1:
                return step

            v = arr[idx]
            step += 1

            for i in keymap[v]:
                if i not in visited:
                    visited.add(i)
                    q.append((step, i))

            del keymap[v]  # important optimization, don't need to visit the same nodes next

            if idx + 1 < len(arr) and (idx + 1) not in visited:
                visited.add(idx + 1)
                q.append((step, idx + 1))
            if idx - 1 >= 0 and (idx - 1) not in visited:
                visited.add(idx - 1)
                q.append((step, idx - 1))