Save Money on Your Trip: Weighted Shortest Path

int findCheapestPrice(int n, int[][] flights, int src, int dst, int K);

int dp(int s, int k);

// Definition: the minimum cost to reach s within k steps starting from src
int dp(int s, int k) {
    // From src to src, no steps are needed
    if (s == src) {
        return 0;
    }
    // If the number of steps is exhausted, there is no solution
    if (k == 0) {
        return -1;
    }

    // ...
}

int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
    // convert the number of transit stops into the number of edges
    K++;
    // ...
    return dp(dst, K);
}

class Solution {
    // Hash table to record the indegree of each node, where the key is the node number
    // and the value is the adjacent nodes pointing to this node along with their
    // to -> [from, price]
    HashMap<Integer, List<int[]>> indegree;
    int src, dst;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        // Convert the number of transit stations into the number of edges
        K++;
        this.src = src;
        this.dst = dst;
        
        indegree = new HashMap<>();
        for (int[] f : flights) {
            int from = f[0];
            int to = f[1];
            int price = f[2];
            // Record which node points to this node and the weight between them
            indegree.putIfAbsent(to, new LinkedList<>());
            indegree.get(to).add(new int[] {from, price});
        }
        
        return dp(dst, K);
    }

    // Definition: the shortest path weight from src to s within k steps
    int dp(int s, int k) {
        // base case
        if (s == src) {
            return 0;
        }
        if (k == 0) {
            return -1;
        }
        // Initialize to the maximum value for easy minimum value extraction later
        int res = Integer.MAX_VALUE;
        if (indegree.containsKey(s)) {
            // When s has indegree nodes, decompose into subproblems
            for (int[] v : indegree.get(s)) {
                int from = v[0];
                int price = v[1];
                // The shortest path weight
                // required to reach the adjacent
                int subProblem = dp(from, k - 1);

                // Skip cases where there is no solution
                if (subProblem != -1) {
                    res = Math.min(res, subProblem + price);
                }
            }
        }
        // If it is still the initial value, it means this node is unreachable
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

class Solution {
    int src, dst;
    HashMap<Integer, List<int[]>> indegree;
    // memoization
    int[][] memo;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        K++;
        this.src = src;
        this.dst = dst;
        // initialize the memoization table with a special value
        memo = new int[n][K + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -888);
        }
        
        indegree = new HashMap<>();
        for (int[] f : flights) {
            int from = f[0];
            int to = f[1];
            int price = f[2];
            indegree.putIfAbsent(to, new LinkedList<>());
            indegree.get(to).add(new int[] {from, price});
        }
        
        return dp(dst, K);
    }

    // definition: the minimum cost to reach s from src within k steps
    int dp(int s, int k) {
        // base case
        if (s == src) {
            return 0;
        }
        if (k == 0) {
            return -1;
        }
        // check the memoization table to prevent redundant calculations
        if (memo[s][k] != -888) {
            return memo[s][k];
        }
        
        // state transition code remains unchanged
        int res = Integer.MAX_VALUE;
        if (indegree.containsKey(s)) {
            for (int[] v : indegree.get(s)) {
                int from = v[0];
                int price = v[1];
                int subProblem = dp(from, k - 1);

                if (subProblem != -1) {
                    res = Math.min(res, subProblem + price);
                }
            }
        }
        // store in the memoization table
        memo[s][k] = res == Integer.MAX_VALUE ? -1 : res;
        return memo[s][k];
    }
}

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        List<int[]>[] graph = new LinkedList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] edge : flights) {
            int from = edge[0];
            int to = edge[1];
            int price = edge[2];
            graph[from].add(new int[]{to, price});
        }

        // start the Dijkstra algorithm
        // calculate the shortest path from src to dst with at most k transfers
        K++;
        return dijkstra(graph, src, K, dst);
    }

    class State {
        // the id of the graph node
        int id;
        // the cost from src node to the current node
        int costFromSrc;
        // the number of nodes passed from src to the current node
        int nodeNumFromSrc;

        State(int id, int costFromSrc, int nodeNumFromSrc) {
            this.id = id;
            this.costFromSrc = costFromSrc;
            this.nodeNumFromSrc = nodeNumFromSrc;
        }
    }

    // input a starting point src, calculate the shortest distance from src to other nodes
    int dijkstra(List<int[]>[] graph, int src, int k, int dst) {
        // definition: the shortest path weight from src to node i is distTo[i]
        int[] distTo = new int[graph.length];
        // definition: the minimum weight path from src to
        // node i must pass through at least nodeNumTo[i]
        int[] nodeNumTo = new int[graph.length];
        Arrays.fill(distTo, Integer.MAX_VALUE);
        Arrays.fill(nodeNumTo, Integer.MAX_VALUE);
        // base case
        distTo[src] = 0;
        nodeNumTo[src] = 0;

        // priority queue, where nodes with smaller costFromSrc come first
        Queue<State> pq = new PriorityQueue<>((a, b) -> {
            return a.costFromSrc - b.costFromSrc;
        });
        // start BFS from the starting point src
        pq.offer(new State(src, 0, 0));

        while (!pq.isEmpty()) {
            State curState = pq.poll();
            int curNodeID = curState.id;
            int costFromSrc = curState.costFromSrc;
            int curNodeNumFromSrc = curState.nodeNumFromSrc;
            
            if (curNodeID == dst) {
                // found the shortest path
                return costFromSrc;
            }
            if (curNodeNumFromSrc == k) {
                // the number of transfers is exhausted
                continue;
            }

            // add the neighbors of curNode to the queue
            for (int[] neighbor : graph[curNodeID]) {
                int nextNodeID = neighbor[0];
                int costToNextNode = costFromSrc + neighbor[1];
                // consume 1 transfer
                int nextNodeNumFromSrc = curNodeNumFromSrc + 1;

                // update the dp table
                if (distTo[nextNodeID] > costToNextNode) {
                    distTo[nextNodeID] = costToNextNode;
                    nodeNumTo[nextNodeID] = nextNodeNumFromSrc;
                }
                // pruning, if the number of transfers is higher
                // and the cost is also higher, it cannot be the
                if (costToNextNode > distTo[nextNodeID]
                    && nextNodeNumFromSrc > nodeNumTo[nextNodeID]) {
                    continue;
                }
                
                pq.offer(new State(nextNodeID, costToNextNode, nextNodeNumFromSrc));
            }
        }
        return -1;
    }
}