787. Cheapest Flights Within K Stops

Posted on Edited on In

787. Cheapest Flights Within K Stops

Description

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1:

1
2
3
4
5
6
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:

1
2
3
4
5
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Example 3:

1
2
3
4
5
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

Constraints:

  • 1 <= n <= 100
  • 0 <= flights.length <= (n * (n - 1) / 2)
  • flights[i].length == 3
  • 0 <= fromi, toi < n
  • fromi != toi
  • 1 <= pricei <= 10^4
  • There will not be any multiple flights between two cities.
  • 0 <= src, dst, k < n
  • src != dst

Hints/Notes

  • 2024/08/13
  • dp
  • No solution from 0x3F

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    vector<vector<pair<int, int>>> graph;
    int dst_;
    // the meaning of dp[i][j]: when we are at i, and there are j stops left,
    // the minium cost to get to dst_
    vector<vector<int>> dp;

    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst,
                          int k) {
        graph.resize(n, vector<pair<int, int>>());
        dp.resize(n, vector<int>(k + 2, -1));
        buildGraph(flights);
        dst_ = dst;
        int res = traverse(src, k + 1);
        return res == INT_MAX ? -1 : res;
    }

    int traverse(int src, int k) {
        if (src == dst_) {
            return 0;
        }
        if (k <= 0) {
            return INT_MAX;
        }
        if (dp[src][k] != -1) {
            return dp[src][k];
        }
        long res = INT_MAX;
        for (auto p : graph[src]) {
            int v = p.first;
            int price = p.second;
            res = min(res, (long)price + traverse(v, k - 1));
        }
        dp[src][k] = res;
        return dp[src][k];
    }

    void buildGraph(vector<vector<int>>& flights) {
        for (auto flight : flights) {
            int from = flight[0];
            int to = flight[1];
            int price = flight[2];
            graph[from].push_back({to, price});
        }
    }
};

Another approach(BFS):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    vector<vector<pair<int, int>>> graph;
    vector<int> costs;

    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst,
                          int k) {
        graph.resize(n, vector<pair<int, int>>());
        costs.resize(n, INT_MAX);
        buildGraph(flights);
        queue<vector<int>> q;
        q.push({src, 0});
        while (!q.empty() && k >= 0) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                auto u = q.front();
                q.pop();
                for (auto p : graph[u[0]]) {
                    int v = p.first, price = p.second;;
                    if (price + u[1] < costs[v]) {
                        costs[v] = price + u[1];
                        q.push({v, costs[v]});
                    }
                }
            }
            k--;
        }
        return costs[dst] == INT_MAX ? -1 : costs[dst];
    }

    void buildGraph(vector<vector<int>>& flights) {
        for (auto flight : flights) {
            int from = flight[0];
            int to = flight[1];
            int price = flight[2];
            graph[from].push_back({to, price});
        }
    }
};