Problem statement

https://binarysearch.com/problems/Border-Crossing/

Solution

Use dijkstra here, where we keep two keys as distance.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, roads, C, start, end):
        def Dijkstra(graph, beg, end):
            q, t = [(0, 0, beg)], {}
            while q:
                steps, time, node = heappop(q)
                if node not in t:
                    t[node] = (steps, time)
                    for v, w in graph[node]:
                        heappush(q, (steps + (d[node] != d[v]), time + w, v))
            return t[end]

        G, d = defaultdict(list), {}
        for i, x in enumerate(C):
            for y in x: d[y] = i

        for x, y, w in roads:
            G[x] += [(y, w)]

        return Dijkstra(G, start, end)