[Python3] Dijkstra
Formalize as a graph problem and interpret (time, digit) as a node, where time is the current cooking time and digit is the digit we have our finger on. The cos
Formalize as a graph problem and interpret (time, digit) as a node, where time is the current cooking time and digit is the digit we have our finger on. The cost of an edge is dependent on whether we use the digit we have our finger on or not. Now apply Dijkstra for sparse graphs.\n\n```python\nclass Solution:\n    def minCostSetTime(self, startAt: int, moveCost: int, pushCost: int, targetSeconds: int) -> int:\n        if targetSeconds == 0:\n            return 0\n        \n        def newState(state, digit):\n            return "".join([state[1:], str(digit)])\n            \n        def stateSecs(state):    \n            minutes = int(state[:2])\n            secs = int(state[2:])\n            return minutes * 60 + secs\n            \n        def neighs(state, finger_digit):\n            for i in range(10):\n                new_state = newState(state, i)\n                if i == finger_digit:\n                    yield (new_state, i, pushCost)\n                else:    \n                    yield (new_state, i, pushCost + moveCost)\n            \n            \n        INF = float("inf")    \n        distance = defaultdict(lambda: INF)        \n        distance[("0000", startAt)] = 0\n        heap = [(0, startAt, "0000")]\n        while heap:\n            d, figdig, state = heapq.heappop(heap)\n            if stateSecs(state) == targetSeconds:\n                return d\n            \n            if d == distance[(state, figdig)]: \n                for new_state, new_finger, cost in neighs(state, figdig):\n                    trydist = d + cost\n                    if trydist < distance[(new_state, new_finger)]:\n                        distance[(new_state, new_finger)] = trydist\n                        heapq.heappush(heap, (trydist, new_finger, new_state))\n        return -1  \n```
['Heap (Priority Queue)']