Problem statement

https://binarysearch.com/problems/Cheapest-Bus-Route/

Solution 1

Let us create graph: start node: (index of bus, end node) from our connections list. Then we perform Dijkstra on this graph. Notice that nodes of our graph G are in fact (idx of bus, location). Notice that price we need to pay is either 1 if we have new bus and 0 if it is the same bus.

Complexity

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

Code

class Solution:
    def solve(self, C):
        G, n = defaultdict(list), -1
        for f, t, idx in C:
            G[f] += [(idx, t)]
            n = max(n, f, t)

        heap, V = [(0, -1, 0)], set()
        while heap:
            cost, idx, e = heappop(heap)
            V.add((idx, e))
            if e == n: return cost

            for idx2, end in G[e]:
                if (idx2, end) in V: continue
                heappush(heap, (cost + (idx != idx2), idx2, end))

        return -1

Solution 2

In fact we can do it with 0-1 weight bfs

Complexity

It is O(E) for time and space.

Code

class Solution:
    def solve(self, C):
        G, n = defaultdict(list), -1
        for f, t, idx in C:
            G[f] += [(idx, t)]
            n = max(n, f, t)

        Q, V = deque([(0, -1, 0)]), set()
        while Q:
            cost, idx, e = Q.popleft()
            V.add((idx, e))
            if e == n: return cost

            for idx2, end in G[e]:
                if (idx2, end) in V: continue
                if idx2 == idx: Q.appendleft((cost, idx2, end))
                else: Q.append((cost + 1, idx2, end))

        return -1