Cheapest Bus Route - Google Top Interview Questions

                        Solution in C++ :

map<int, map<int, vector<int>>>
    edges;           // edges[i][j] gives all locations k, for stop i and bus id j
int mindp[1005];     // mindp[i] = min cost from stop i
int dp[1005][1005];  // dp[i][j] = cost of being at station i with
bool minused[1005];  // have we tried transferring out of station i yet?
int solve(vector<vector<int>>& connections) {
    int n = 0;
    edges.clear();
    int m = 0;
    for (auto& e : connections) {
        n = max(n, e[0] + 1);
        n = max(n, e[1] + 1);
        m = max(m, e[1] + 1);
        edges[e[0]][e[2]].push_back(e[1]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dp[i][j] = 1e9;
        }
    }
    for (int i = 0; i < n; i++) minused[i] = false;
    mindp[0] = 0;
    for (int i = 1; i < n; i++) mindp[i] = 1e9;
    deque<pair<int, int>> q;
    for (int i = 0; i < m; i++) {
        dp[0][i] = 1;
        q.emplace_back(0, i);
    }
    while (q.size()) {
        int curr = q.front().first;
        int currbus = q.front().second;
        q.pop_front();
        // stay on the same bus
        for (int loc : edges[curr][currbus]) {
            int cost = min(mindp[curr] + 1, dp[curr][currbus]);
            if (cost < dp[loc][currbus]) {
                dp[loc][currbus] = cost;
                q.emplace_front(loc, currbus);
            }
            mindp[loc] = min(mindp[loc], dp[loc][currbus]);
        }
        if (!minused[curr]) {
            // try all routes out
            for (auto e : edges[curr]) {
                int busid = e.first;
                for (int loc : e.second) {
                    int cost = min(mindp[curr] + 1, dp[curr][busid]);
                    if (cost < dp[loc][busid]) {
                        dp[loc][busid] = cost;
                        q.emplace_back(loc, busid);
                    }
                    mindp[loc] = min(mindp[loc], dp[loc][busid]);
                }
            }
            minused[curr] = true;
        }
    }
    if (mindp[n - 1] == 1e9) return -1;
    return mindp[n - 1];
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[][] connections) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return Integer.compare(a[1], b[1]);
            }
        });
        // first element is the node, second element is shortest distance from 0 to that node
        // last element(or third element) is BUS ID
        Map<Integer, Set<State>> graph = new HashMap();
        int maxy = -1;
        int max_id = -1;
        for (int[] con : connections) {
            graph.putIfAbsent(con[0], new HashSet());
            graph.get(con[0]).add(new State(con[1], con[2]));

            maxy = Math.max(maxy, Math.max(con[0], con[1]));
            max_id = Math.max(max_id, con[2]);
        }
        // System.out.println("graph is " + graph.toString());
        int[][] ref = new int[maxy + 1][max_id + 1];
        for (int[] x : ref) Arrays.fill(x, Integer.MAX_VALUE);
        for (int j = 0; j < ref[0].length; j++) {
            ref[0][j] = 0;
        }
        boolean[][] vis = new boolean[maxy + 1][max_id + 1];

        if (!graph.containsKey(0)) {
            return -1;
        }
        for (State start : graph.get(0)) {
            pq.offer(new int[] {0, 0, start.bus});
        }
        while (!pq.isEmpty()) {
            int[] promising = pq.poll();
            int node = promising[0];
            int weight = promising[1];
            int curr_bus = promising[2];
            if (vis[node][curr_bus] || ref[node][curr_bus] < weight)
                continue;
            vis[node][curr_bus] = true;
            if (!graph.containsKey(node))
                continue;
            for (State neighbor : graph.get(node)) {
                int new_dist = weight;
                if (neighbor.bus != curr_bus) {
                    new_dist++;
                }
                int new_node = neighbor.neighbor;
                if (ref[new_node][neighbor.bus] > new_dist) {
                    pq.offer(new int[] {new_node, new_dist, neighbor.bus});
                    ref[new_node][neighbor.bus] = new_dist;
                }
            }
        }
        // System.out.println(Arrays.deepToString(ref));
        int ret = Integer.MAX_VALUE;
        for (int x : ref[maxy]) {
            ret = Math.min(ret, x);
        }
        if (ret == Integer.MAX_VALUE)
            return -1;
        return ret + 1;
    }
}
class State {
    int neighbor;
    int bus;
    public State(int neighbor, int bus) {
        this.neighbor = neighbor;
        this.bus = bus;
    }
    @Override
    public String toString() {
        return neighbor + " " + bus;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, routes):
        s = 0
        target_end = float("-inf")

        for route in routes:
            target_end = max(target_end, route[0])
            target_end = max(target_end, route[1])

        if s == target_end:
            return 0

        graph = collections.defaultdict(list)

        for start, end, id in routes:
            graph[start].append((id, end))

        pq = []

        for id, end in graph[s]:
            heapq.heappush(pq, (1, id, end))

        visited = set()

        while pq:
            cost, id, e = heapq.heappop(pq)
            visited.add((id, e))

            if e == target_end:
                return cost

            for connected_id, end in graph[e]:
                if (connected_id, end) in visited:
                    continue

                if id == connected_id:
                    heapq.heappush(pq, (cost, connected_id, end))
                else:
                    heapq.heappush(pq, (cost + 1, connected_id, end))

        return -1