K站中转站内最便宜的航班

目录

方法一：dfs+减枝

方法二：动态规划

基础知识补充：const和constexpr的区别

题目出处：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/

方法一：dfs+减枝

思路：用vector<vector<pair<int, int>>> 记录下有向带权图。从起点开始进行深度优先遍历。

1. 最多经过k个中转站，可以转化为最多经过k+1个城市。
2. 使用站点数和每次的花费进行减枝。

class Solution {
private:int ans = INT_MAX;    
public:void dfs(int node, int& end, int& k, int count, int price, vector<vector<pair<int,int>>>& graph, vector<bool>& vis){if(node == end && count <= k){ans = min(ans, price);return;  }for(auto & [neibor, w] : graph[node]){if(count > k || price > ans){continue;}if(!vis[neibor]){vis[neibor] = true;dfs(neibor, end, k, count+1, price+w, graph, vis);vis[neibor] = false;  }}}int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {vector<bool> vis(n, false);vector<vector<pair<int, int>>> graph(n);for(auto & flight : flights){graph[flight[0]].push_back({flight[1], flight[2]});}int count = 0; int price = 0;int step = k+1;dfs(src, dst, step, count, price ,graph, vis);if(ans == INT_MAX){ans = -1; } return ans;}
};

方法二：动态规划

思路：f[t][i]表示通过恰好t次航班，从出发城市src到城市i需要的最小花费，显然max(t) = k+1。

状态转移：  f[t][i]=min{ f[t-1][j] + cost(j,i) }，其中(j,i)是j到i的一条边、属于flights

结果：题中要求最多只能有k个中转站，也就是最多搭乘k+1次航班，所以最终的答案是max{f[1[dst], f[2][dst], ..., f[k+1][dst]}

class Solution {
private:static constexpr int INF = 10000 * 101 + 1; 
//根据题目中给出的数据范围，航班的花费不超过 10^4，最多搭乘航班的次数不超过101public:int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {vector<vector<int>> f(k + 2, vector<int>(n, INF));f[0][src] = 0;for (int t = 1; t <= k + 1; ++t) {for (auto&& flight: flights) {int j = flight[0], i = flight[1], cost = flight[2];f[t][i] = min(f[t][i], f[t - 1][j] + cost);}}int ans = INF;for (int t = 1; t <= k + 1; ++t) {ans = min(ans, f[t][dst]);}return (ans == INF ? -1 : ans);}
};

基础知识补充：const和constexpr的区别

const：修饰的变量是"只读"属性

constexpr：修饰的变量是常量语义(常量或者常量表达式)

C++ 11标准中，为了解决 const 关键字的双重语义问题，保留了 const 表示“只读”的语义，而将“常量”的语义划分给了新添加的 constexpr 关键字。使用是建议将 const 和 constexpr 的功能区分开，即若表达“只读”语义的场景使用 const，表达“常量”语义的场景使用constexpr。