旅游省钱大法：加权最短路径 :: labuladong的算法小抄 #1005
Replies: 23 comments 8 replies
-
|
这里的k的判断其实是有问题的吧？k==0只是代表没有了中转的机会，并不是不可达(还可直接从起点到终点)，所以应该将if (k == 0)改为if (k < 0)吧？ |
Beta Was this translation helpful? Give feedback.
-
|
请问一下各位，
|
Beta Was this translation helpful? Give feedback.
-
|
我一开始也不太理解为什么k要加一，看了东哥的解释加上题目的限制条件后，感觉是没问题的。 起始k不加1的解法，将if (k == 0)改为if (k < 0)。我自己理解起来比较自然。 class Solution {
int n, src, dst;
int[][] flights;
int[][] memo;
HashMap<Integer, List<int[]>> indegree = new HashMap<>();
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
this.n = n;
this.flights = flights;
this.src = src;
this.dst = dst;
// 求入度
for(int[] flight : flights){
int from = flight[0], to = flight[1], price = flight[2];
indegree.putIfAbsent(to, new ArrayList<>());
indegree.get(to).add(new int[]{from, price});
}
memo = new int[n][k + 1];
for(int[] arr : memo){
Arrays.fill(arr, -2);
}
return dp(dst, k);
}
int dp(int dst, int k){
if(src == dst){
return 0;
}
if(k < 0){
return -1;
}
if(memo[dst][k] != -2){
return memo[dst][k];
}
int res = Integer.MAX_VALUE;
if(indegree.containsKey(dst)){
for(int[] v : indegree.get(dst)){
int subProblem = dp(v[0], k - 1);
if(subProblem == -1) continue;
res = Math.min(res, subProblem + v[1]);
}
}
memo[dst][k] = res == Integer.MAX_VALUE ? -1 : res;
return memo[dst][k];
}
} |
Beta Was this translation helpful? Give feedback.
-
|
k+1 是为了边。。。每次递归都算是走了一条边，如果走到k=0，但是这个节点不是起点，那就代表已经走了k（就是原始的没加1的k值）个点了 |
Beta Was this translation helpful? Give feedback.
-
|
另外其实还有另外一种思路，即倒着过来求，将dp定义为dp(int start, int k)，即当前中转次数为k时，从start到dst的最短路径，对应的dp要更改为 // 在中转次数为k的情况下从start到dst的最短路径
public int dp(int start, int k) {
if (start == dst) {
return 0;
}
if (k > this.k) {
return -1;
}
if (memo[start][k] != -666) {
return memo[start][k];
}
int res = Integer.MAX_VALUE;
if (outdegree.containsKey(start)) {
for (int[] element : outdegree.get(start)) {
int to = element[0];
int price = element[1];
int subProblem = dp(to, k + 1);
if (subProblem == -1) continue;
res = Math.min(res, subProblem + price);
}
}
memo[start][k] = res == Integer.MAX_VALUE ? -1 : res;
return memo[start][k];
}此时也要注意对k的判断 |
Beta Was this translation helpful? Give feedback.
-
|
@LovesAsuna 嗯， 1、这种边界问题的关键是看题目给的数据边界，题目说了 2、我们在一开始给输入的 |
Beta Was this translation helpful? Give feedback.
-
|
@LovesAsuna 我上面说的是 是的，这就是我们找到答案的时候，实际上这种情况算法也没有返回 -1，而是返回了 0，因为判断 |
Beta Was this translation helpful? Give feedback.
-
|
呜呜呜看了这节的题目没看大佬分析，自己尝试自己分析一下，没想到真的写出来了，写的代码有些粗糙劣质~~现在就去完善，谢谢大佬 class Solution {
int[][] memo;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
memo = new int[n+1][k+2];
return dp(n, flights, src, dst, k+1);
}
public int dp(int n, int[][] flights, int src, int dst, int k){
// base case
if(k < 0){
return -1;
}else if(src == dst){
return 0;
}
if(memo[src][k] != 0){
return memo[src][k];
}
int res = Integer.MAX_VALUE;
for(int[] f : flights){
if(f[0] != src)
continue;
int subProblem = dp(n, flights, f[1], dst, k-1);
if(subProblem == -1){
continue;
}
res = Math.min(res, subProblem + f[2]);
}
memo[src][k] = res==Integer.MAX_VALUE?-1:res;
return memo[src][k];
}
} |
Beta Was this translation helpful? Give feedback.
-
|
一开始不太理解为什么你的做法代码量这么简洁，不用像东哥求入度。现在明白了。 两种做法的子问题定义不一样。 以上是我个人粗浅的见解 |
Beta Was this translation helpful? Give feedback.
-
|
自己又把两种思路写了一下，具有对称性，很妙。 求入度class Solution {
int n, src, dst;
int[][] flights;
int[][] memo;
HashMap<Integer, List<int[]>> indegree = new HashMap<>();
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
this.n = n;
this.flights = flights;
this.src = src;
this.dst = dst;
// 求入度
for(int[] flight : flights){
int from = flight[0], to = flight[1], price = flight[2];
indegree.putIfAbsent(to, new ArrayList<>());
indegree.get(to).add(new int[]{from, price});
}
memo = new int[n][k + 1];
for(int[] arr : memo){
Arrays.fill(arr, -2);
}
return dp(dst, k);
}
int dp(int dst, int k){
if(src == dst){
return 0;
}
if(k < 0){
return -1;
}
if(memo[dst][k] != -2){
return memo[dst][k];
}
int res = Integer.MAX_VALUE;
if(indegree.containsKey(dst)){
for(int[] v : indegree.get(dst)){
int subProblem = dp(v[0], k - 1);
if(subProblem == -1) continue;
res = Math.min(res, subProblem + v[1]);
}
}
memo[dst][k] = res == Integer.MAX_VALUE ? -1 : res;
return memo[dst][k];
}
}求出度class Solution {
int n, src, dst;
int[][] flights;
int[][] memo;
HashMap<Integer, List<int[]>> outdegree = new HashMap<>();
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
this.n = n;
this.flights = flights;
this.src = src;
this.dst = dst;
// 求出度
for(int[] flight : flights){
int from = flight[0], to = flight[1], price = flight[2];
outdegree.putIfAbsent(from, new ArrayList<>());
outdegree.get(from).add(new int[]{to, price});
}
memo = new int[n][k + 1];
for(int[] arr : memo){
Arrays.fill(arr, -2);
}
return dp(src, k);
}
int dp(int src, int k){
if(src == dst){
return 0;
}
if(k < 0){
return -1;
}
if(memo[src][k] != -2){
return memo[src][k];
}
int res = Integer.MAX_VALUE;
if(outdegree.containsKey(src)){
for(int[] v : outdegree.get(src)){
int subProblem = dp(v[0], k - 1);
if(subProblem == -1) continue;
res = Math.min(res, subProblem + v[1]);
}
}
memo[src][k] = res == Integer.MAX_VALUE ? -1 : res;
return memo[src][k];
}
} |
Beta Was this translation helpful? Give feedback.
-
|
@zzbb9944 千里之行，始于足下，加油！ |
Beta Was this translation helpful? Give feedback.
-
|
这个自底向上的方法 ，比较难想清楚，因为这里的i，j 和之前的dp问题不太一样了，这里的i表示中转次数，比较抽象，且要注意 最后需要对最后一行的结果进行求最小值，不懂的，自己画个二维数组看看。 这个比较抽象，如果看不明白，还是看东哥的解答。 class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int[][] dp = new int[k+1][n];// [i][j] 表示 从 开始节点 到 j节点 中转 i次的最少价格
for(int i = 0; i<k+1;i++){
Arrays.fill(dp[i],10000*101+1);//全部初始化成为 无法取到的值
//这里为什么初始化成这个样子 需要看看题目里面的限制
//但是如果初始化成 MAX_VALUE 是有bug的 会数值溢出 具体什么原因 自己想
}
for(int[] flight: flights){
int from = flight[0];
int to = flight[1];
int cost = flight[2];
if(src == from){
dp[0][to] = cost;
//中转0 次 从 开始节点 到 to这个节点的花费
}
}
//中转 i次
for(int i = 1;i<k+1;i++){
for(int[] flight : flights){
int from = flight[0];
int to = flight[1];
int cost = flight[2];
//从开始节点 中转 i 次 到达 to 需要的最少花费
//在两种中做选择
//从开始处 中转i-1次到达 from(to的前一个节点) 然后 再从前一个节点 到达目标节点位置
//dp[i][to] 有多种方式到达 to ，这个里面 有最小值 也可能有最大值 反正直接比较就完事了
dp[i][to] = Math.min(dp[i][to],dp[i-1][from]+cost);
}
}
int result = 10000*101+1;
//在所有可能中 找到到达 dst 位置的 最小的cost 作为结果
for(int i = 0; i<k+1;i++){
result = Math.min(result,dp[i][dst]);
}
return result == 10000*101+1 ? -1: result;
}
} |
Beta Was this translation helpful? Give feedback.
-
|
提供一个较粗糙的C++版本的实现，供参考。 class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
//梳理数据结构
vector<vector<int>> graphs(n,vector<int>());
vector<vector<int>> weights(n,vector<int>(n,-1));
for(int i=0;i<flights.size();++i){
graphs[flights[i][1]].emplace_back(flights[i][0]);
weights[flights[i][0]][flights[i][1]]=flights[i][2];
}
//动态规划算法
vector<vector<int>> mem(n,vector<int>(k+1,-1));
int res=dp(src,dst,k,graphs,weights,mem);
return res!=1e9?res:-1;
}
int dp(int from,int to,int k,vector<vector<int>> & graphs,vector<vector<int>>& weights,vector<vector<int>> &mem){
if(from==to) return 0;
if(k<0) return 1e9;
if(mem[to][k]!=-1) return mem[to][k];
int res=1e9;
for(int i=0;i<graphs[to].size();++i){
int candidate=graphs[to][i];
res=std::min(res,dp(from,candidate,k-1,graphs,weights,mem)+weights[candidate][to]);
}
mem[to][k]=res;
return mem[to][k];
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
Javascript BFS版本: var findCheapestPrice = function(n, flights, src, dst, k) {
// 构建邻接表
const map = new Array(n).fill(0).map((_, i) => ({id: i, edges: []}))
flights.forEach(flight => {
const [from, to, price] = flight
map[from].edges.push({to, price})
})
let res = new Array(n).fill(Number.MAX_SAFE_INTEGER)
let depth = 0; // 记录深度中转站
let q = [] // TODO: 换成优先级队列
q.push([src, 0])
// BFS
while(q.length && depth <= k + 1) {
let len = q.length
while (len) {
const [cur, curPrice] = q.shift()
len--
if (curPrice >= res[cur]) continue
res[cur] = curPrice
for(const edge of map[cur].edges) {
q.push([edge.to, edge.price + curPrice])
}
}
depth++
}
return res[dst] === Number.MAX_SAFE_INTEGER ? -1 : res[dst]
}; |
Beta Was this translation helpful? Give feedback.
-
自己该自己的代码 ， 之前的代码感觉写的不够精简， 重构一下 class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
// dp[i][j] 表示 经过 j个中转站到达 i 的最低费用
//k+1+1 的原因是 将最后一个节点也理解成中转节点
int[][] dp = new int[n][k+2];
//初始化 ， 到达所有节点的初始化为 最大值 ， 因为要求最低费用
for(int i = 0 ; i< n ; i++){
Arrays.fill(dp[i],Integer.MAX_VALUE);
}
for(int j = 0; j< k+2 ; j++){
dp[src][j] = 0;//任何src 到src 最小都是 0
}
for(int j = 1; j< k+2 ; j++){
for(int[] flight : flights){
/*
flight[0] form
flight[1] to
flight[2] wight
*/
//这一步防止后面的dp[flight[0]][j-1] + flight[2] 这一步出现 Integer.MAX_VALUE 参加运算 出现 数值溢出现象
//也可以在初始化的时候 初始化成一个较大的数 不一定是Integer.MAX_VALUE
if(dp[flight[0]][j-1] == Integer.MAX_VALUE){
continue;
}
dp[flight[1]][j] = Math.min(dp[flight[1]][j],dp[flight[0]][j-1] + flight[2]);
}
}
return dp[dst][k+1] == Integer.MAX_VALUE ? -1 : dp[dst][k+1];
}
} |
Beta Was this translation helpful? Give feedback.
-
|
我是使用边的思想来理解，首先将问题中的
最多 此时 这样 base case 也很易于理解： 最后返回的是 |
Beta Was this translation helpful? Give feedback.
-
|
贴个C++解法，状态选的是K和起点而非K和终点(结果相同)，用二维数组+pair类型直接构造有向加权图，常规DP class Solution {
vector<vector<int>> memo;
vector<vector<pair<int, int>>> graph;
public:
void buildGraph(vector<vector<int>>& flights, int n) {
graph.assign(n, vector<pair<int, int>>());
for (auto flight: flights) {
int from = flight[0];
int to = flight[1];
int price = flight[2];
graph[from].emplace_back(to, price);
}
}
// 函数返回从src到dst的最多经过K次中转的最便宜价格
int dp(vector<vector<pair<int, int>>>& graph, int src, int dst, int k) {
if (src == dst) return 0; // base case
if (k == -1) return INT_MAX; // 达到中转上限
if (memo[src][k] != -1) return memo[src][k];
int res = INT_MAX;
for (auto neighbor: graph[src]) {
int node = neighbor.first;
int price = neighbor.second;
int subProb = dp(graph, node, dst, k - 1);
if (subProb == INT_MAX) continue;
res = min(res, subProb + price);
}
return memo[src][k] = res;
}
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
buildGraph(flights, n);
memo.assign(n, vector<int> (k + 1, -1));
int res = dp(graph, src, dst, k);
return res == INT_MAX ? -1 : res;
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
python # 计算每个节点的入度以及对应价格
indegree = {}
for item in flights:
start, to, price = item[0], item[1], item[2]
if to not in indegree:
indegree[to] = []
indegree[to].append([start, price])
k += 1 # k个stop = k+1条边，将中转站个数转化成边的条数
memo = [[-1 for _ in range(k+1)] for __ in range(n)]
# dp定义：从 src 出发，大K 步之内到达 end 的最短路径权重
def dp(end, K):
nonlocal src, indegree, memo
# base case
if end == src:
return 0
if K == 0: # 没有剩余步数了
return -1
if memo[end][K] != -1:
return memo[end][K]
res = float('inf') # 初始化：K步内src到end到最短权重路径
# 只有当end节点有入度时，才是可以到达点路径
if end in indegree:
for sub in indegree[end]:# 分解问题
start, price = sub[0], sub[1]
# 从src到达end前置节点所需的最短路径权重
subProblem = dp(start, K-1)
if subProblem != -1: # 跳过无解问题
res = min(res, subProblem+price)
memo[end][K] = res if res != float('inf') else -1
return memo[end][K]
return dp(dst, k) |
Beta Was this translation helpful? Give feedback.
-
|
自己做这道题想的是用 i j k 三个状态写的自底向上，做题时想不出更灵巧的状态，用简单的状态去凑，处于超时的边缘： class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
// 存储节点 j 的入边 toedges[j] = [[i0, j, price0], [i1, j, price1], ...]
vector<vector<vector<int>>> toedges(n);
// dp[i][j][k] 表示从 i 到 j 经过 k 次中转的最低价格
vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(k+1, INT_MAX-10000))); // INT_MAX-10000 防止溢出
// base case:
// k == 0 时，最低价格等于直航
for(auto e : flights) {
int i = e[0];
int j = e[1];
int price = e[2];
dp[i][j][0] = price;
toedges[j].push_back(e);
}
for(int kk = 1; kk <= k; kk++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i == j) continue;
for(vector<int>& e : toedges[j]) {
// 遍历每一条 j 的入边
int prej = e[0];
// 状态转移：
if(prej != i)
dp[i][j][kk] = min(dp[i][j][kk], dp[i][prej][kk-1] + e[2]); // INT_MAX-10000 防止这儿溢出
else
dp[i][j][kk] = min(dp[i][j][kk], dp[i][j][kk-1]);
}
}
}
}
return dp[src][dst][k] == INT_MAX-10000 ? -1 : dp[src][dst][k];
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
cool，这个解法的穷举的思路已经有了，就是优化技巧可能有些不熟练。 一般来说，对于指定 |
Beta Was this translation helpful? Give feedback.
-
|
捉个小虫，Dijkstra里，可以通过比较转机次数来保证处理最小cost且最小转机次数 修改后 // 输入一个起点 src，计算从 src 到其他节点的最短距离
int dijkstra(List<int[]>[] graph, int src, int k, int dst) {
// 定义：从起点 src 到达节点 i 的最短路径权重为 distTo[i]
int[] distTo = new int[graph.length];
// 定义：从起点 src 到达节点 i 至少要经过 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;
// 优先级队列，costFromSrc 较小的排在前面
Queue<State> pq = new PriorityQueue<>((a, b) -> {
if (a.costFromSrc == b.costFromSrc) {
return a.nodeNumFromSrc - b.nodeNumFromSrc;
}
return a.costFromSrc - b.costFromSrc;
});
// 从起点 src 开始进行 BFS
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) {
// 找到最短路径
return costFromSrc;
}
if (curNodeNumFromSrc == k) {
// 中转次数耗尽
continue;
}
// 将 curNode 的相邻节点装入队列
for (int[] neighbor : graph[curNodeID]) {
int nextNodeID = neighbor[0];
int costToNextNode = costFromSrc + neighbor[1];
// 中转次数消耗 1
int nextNodeNumFromSrc = curNodeNumFromSrc + 1;
// 剪枝，如果中转次数更多，花费还更大，那必然不会是最短路径
if (costToNextNode > distTo[nextNodeID]
&& nextNodeNumFromSrc > nodeNumTo[nextNodeID]) {
continue;
}
pq.offer(new State(nextNodeID, costToNextNode, nextNodeNumFromSrc));
// 更新 dp table
distTo[nextNodeID] = costToNextNode;
nodeNumTo[nextNodeID] = nextNodeNumFromSrc;
}
}
return -1;
}原版 // 输入一个起点 src，计算从 src 到其他节点的最短距离
int dijkstra(List<int[]>[] graph, int src, int k, int dst) {
// 定义：从起点 src 到达节点 i 的最短路径权重为 distTo[i]
int[] distTo = new int[graph.length];
// 定义：从起点 src 到达节点 i 至少要经过 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;
// 优先级队列，costFromSrc 较小的排在前面
Queue<State> pq = new PriorityQueue<>((a, b) -> {
return a.costFromSrc - b.costFromSrc;
});
// 从起点 src 开始进行 BFS
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) {
// 找到最短路径
return costFromSrc;
}
if (curNodeNumFromSrc == k) {
// 中转次数耗尽
continue;
}
// 将 curNode 的相邻节点装入队列
for (int[] neighbor : graph[curNodeID]) {
int nextNodeID = neighbor[0];
int costToNextNode = costFromSrc + neighbor[1];
// 中转次数消耗 1
int nextNodeNumFromSrc = curNodeNumFromSrc + 1;
// 更新 dp table
if (distTo[nextNodeID] > costToNextNode) {
distTo[nextNodeID] = costToNextNode;
nodeNumTo[nextNodeID] = nextNodeNumFromSrc;
}
// 剪枝，如果中转次数更多，花费还更大，那必然不会是最短路径
if (costToNextNode > distTo[nextNodeID]
&& nextNodeNumFromSrc > nodeNumTo[nextNodeID]) {
continue;
}
pq.offer(new State(nextNodeID, costToNextNode, nextNodeNumFromSrc));
}
}
return -1;
} |
Beta Was this translation helpful? Give feedback.
-
|
打卡，打卡。 dp[s, k] 表示k步内从src到达s的最小路径权重. |
Beta Was this translation helpful? Give feedback.
-
|
dp table c++版本 class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
unordered_map<int, vector<pair<int, int>>> m;
for(auto flight: flights){
int from = flight[0];
int to = flight[1];
int w = flight[2];
if(m.find(to) != m.end()){
m[to].push_back(pair<int, int> (from, w));
}
else{
m[to] = vector<pair<int, int>> (1, pair<int, int> (from, w));
}
}
// dp[i][j]表示中转次数为i时，从src到达城市j的最少花费
vector<vector<int>> dp(k + 1, vector<int> (n, 0));
// base case dp[0][j]
for(int j = 0; j < n; j++){
// 原地不动
if(j == src){
dp[0][j] = 0;
continue;
}
// 找到从src到j的航线
if(m.find(j) != m.end()){
for(auto flight: m[j]){
if(flight.first == src){
dp[0][j] = flight.second;
}
}
// 没有从src到j的航线
if(dp[0][j] == 0) dp[0][j] = -1;
}
else{
// 没有到j的航线
dp[0][j] = -1;
}
}
for(int i = 1; i <= k; i++){
for(int j = 0; j < n; j++){
int res = INT_MAX;
// 原地不动
if(j == src){
dp[i][j] = 0;
continue;
}
// 遍历所有可能航线
for(auto flight: m[j]){
if(dp[i-1][flight.first] == -1) continue;
res = min(res, dp[i-1][flight.first] + flight.second);
}
dp[i][j] = res == INT_MAX ? -1: res;
}
}
return dp[k][dst];
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
东哥，想问下Dijkstra解法中 nodeNumTo 数组的正确定义。文中你给的定义是 “从起点 src 到达节点 i 至少要经过 nodeNumTo[i] 个节点”，是不是就相当于从src到i的最少节点数。但是我理解 nodeNumTo 数组应该是记录对应distTo[i] 的最短路径要经过的节点数（是不是并不一定是最少节点数呢？），因为侯文nodeNumTo[i] 只有在更新distTo[i]的时候才会同步更新。想问这样的理解正确吗？ |
Beta Was this translation helpful? Give feedback.
-
|
我理解你的意思了，你是对的，是我表述的不准确，已修改。 |
Beta Was this translation helpful? Give feedback.
-
|
没人用备忘录的么，刷题小白第一时间想到的是自顶至下搜索 class Solution {
public:
int trace(unordered_map<int, vector<vector<int>>>& dp, int src, int dst, int k/*k为走过的边数*/, vector<vector<int>>& memo){
if(src == dst) return 0;
if(k == 0) return INT_MAX;
if(memo[src][k] != 88888) return memo[src][k];
for(int i=0; i<dp[src].size(); ++i){
int tmp = trace(dp, dp[src][i][0], dst, k-1, memo);
tmp = tmp==INT_MAX ? INT_MAX : tmp+dp[src][i][1];
memo[src][k] = min(memo[src][k], tmp);
}
if(memo[src][k] == 88888) memo[src][k] = INT_MAX;
return memo[src][k];
}
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
unordered_map<int, vector<vector<int>>> dp;
for(int i=0; i<flights.size(); ++i){
dp[flights[i][0]].push_back({flights[i][1], flights[i][2]});
}
vector<vector<int>> memo(n, vector<int>(k+2, 88888));
int res = trace(dp, src, dst, k+1, memo);
return res==INT_MAX ? -1:res;
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
js 的 dp table 解法，首先将问题中的最多 // 问题等价: 最多 k∈[0,n) 个节点中转等价为最多 k + 1 条边
// dp[i][j] 代表 src 经过 i 条边到达 j 的最小 price
var findCheapestPrice = function (n, flights, src, dst, k) {
const dp = new Array(k + 2).fill(0).map(() => new Array(n).fill(Infinity))
// base case: src 经过任意取值的 j 条边到达 src 的最小 price 均为 0
for (let i = 0; i <= k + 1; i++) dp[i][src] = 0
for (let i = 1; i <= k + 1; i++) {
for (const flight of flights) {
const [from, to, price] = flight
dp[i][to] = Math.min(dp[i][to], dp[i - 1][from] + price)
}
}
return dp[k + 1][dst] === Infinity ? -1 : dp[k + 1][dst]
} |
Beta Was this translation helpful? Give feedback.
-
|
求助大佬们，leetcode 2093. Minimum Cost to Reach City With Discounts和本题比较类似，主要区别在于2093是无向图。想请各位一起讨论一下2093能否用类似本题的dp解法求解？ |
Beta Was this translation helpful? Give feedback.
-
|
787题也可以用Bellman-Ford算法（单源最短路径），维护一个最短路径数组。因为题目中有k个中转的限制，所有需要在Bellman-Ford稍作修改，下面是Java代码实现: class Solution {
/**
* 贝尔曼福特法
* @param n
* @param flights
* @param src
* @param dst
* @param k
* @return
*/
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
final int MAX = Integer.MAX_VALUE/2;// 防止两个MAX相加溢出所以除以二
int[][] graph = new int[n][n];// 邻接矩阵
// 邻接矩阵初始化start
for (int i = 0; i < n;i++){
for(int j = 0; j < n;j++){
if(i==j)graph[i][j]=0;
else graph[i][j] = MAX;
}
}
for(int i = 0; i < flights.length; i++){
int start = flights[i][0];
int end = flights[i][1];
int weight = flights[i][2];
graph[start][end] = weight;
}
// 邻接矩阵初始化end
int[] fpath = new int[n];// 其中存储了src到任意节点的距离
for(int i = 0; i < fpath.length; i++){
fpath[i] = MAX; // 初始化到其他节点为MAX
}
fpath[src] = 0;// src到src的距离为0
// Bellman-Ford算法开始，不断优化fpath这个一维数组
for(int i = 1; i <= k+1; i++){// 如果题目中不限制k，则i<=点数-1
// 复制上一次的迭代结果
int[] clone = fpath.clone();// 使得当前次寻找只在上一次结果的基础上，只能找到经过i条边的最短路径，从而是k+1发挥作用
for(int f= 0; f < flights.length; f++){// 遍历所有边（也可以遍历graph邻接矩阵中存储的每条边）
int start = flights[f][0];
int end = flights[f][1];
int weight = flights[f][2];
fpath[end] = Math.min(fpath[end],clone[start]+weight);// 如果题目中不限制k，则无须用clone 直接用fpath即可
}
}
return fpath[dst]>=MAX ? -1:fpath[dst];
}
} |
Beta Was this translation helpful? Give feedback.
-
|
哈希分组+备忘录递归 class Solution {
int[][] memo;
Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
memo = new int[n + 1][k + 1];
for (int i = 0; i < flights.length; i++) {
int f = flights[i][0];
int t = flights[i][1];
int p = flights[i][2];
map.putIfAbsent(f, new HashMap<>());
map.get(f).put(t, p);
}
for (int[] a : memo) {
Arrays.fill(a, -2);
}
return dp(flights, src, dst, k);
}
public int dp(int[][] flights, int src, int dst, int k) {
if (k < 0) {
return src == dst ? 0 : -1;
}
//如果等于dst直接返回
if (src == dst) {
return 0;
}
if (memo[src][k] != -2) {
return memo[src][k];
}
//是否包含直达的路径
Map<Integer, Integer> path = map.get(src);
//不可达
if (path == null) return -1;
int min = Integer.MAX_VALUE;
for (Map.Entry<Integer, Integer> entry : path.entrySet()) {
int key = entry.getKey();
int val = entry.getValue();
int res = dp(flights, key, dst, k - 1);
if (res >= 0) {
min = Math.min(min, res + val);
}
}
min = min == Integer.MAX_VALUE ? -1 : min;
memo[src][k] = min;
return min;
}
} |
Beta Was this translation helpful? Give feedback.
and others
-
文章链接点这里：旅游省钱大法：加权最短路径
评论礼仪 见这里，违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions