前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-04-28:有 n 个城市通过一些航班连接。给你一个数组 flights ,其中 flights[i] = [from

2022-04-28:有 n 个城市通过一些航班连接。给你一个数组 flights ,其中 flights[i] = [from

作者头像
福大大架构师每日一题
发布2022-06-04 10:38:10
3210
发布2022-06-04 10:38:10
举报

2022-04-28:有 n 个城市通过一些航班连接。给你一个数组 flights ,其中 flights[i] = [fromi, toi, pricei] ,表示该航班都从城市 fromi 开始,以价格 pricei 抵达 toi。

现在给定所有的城市和航班,以及出发城市 src 和目的地 dst,你的任务是找到出一条最多经过 k 站中转的路线,使得从 src 到 dst 的 价格最便宜 ,并返回该价格。如果不存在这样的路线,则输出 -1。

输入:

n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]

src = 0, dst = 2, k = 1

输出: 200

力扣787. K 站中转内最便宜的航班。

答案2022-04-28:

类似于宽度优先遍历。Bellman Ford算法,可以处理负边,但不能处理负数环。

代码用rust编写。代码如下:

代码语言:javascript
复制
fn main() {
    let n: isize = 3;
    let mut edges: Vec<Vec<isize>> = vec![vec![0, 1, 100], vec![1, 2, 100], vec![0, 2, 500]];
    let src: isize = 0;
    let dst: isize = 2;
    let k: isize = 1;
    let ans = find_cheapest_price2(n, &mut edges, src, dst, k);
    println!("ans = {}", ans);
}

fn find_cheapest_price2(
    n: isize,
    flights: &mut Vec<Vec<isize>>,
    src: isize,
    dst: isize,
    k: isize,
) -> isize {
    let mut cost: Vec<isize> = vec![];
    for _k in 0..n {
        cost.push(9223372036854775807);
    }
    cost[src as usize] = 0;
    for _i in 0..=k {
        let mut next: Vec<isize> = vec![];
        for j in 0..n {
            next.push(cost[j as usize]);
        }
        for j in 0..flights.len() {
            if cost[(flights[j as usize][0]) as usize] != 9223372036854775807 {
                next[(flights[j as usize][1]) as usize] = get_min(
                    next[(flights[j as usize][1]) as usize],
                    cost[(flights[j as usize][0]) as usize] + flights[j as usize][2],
                );
            }
        }
        cost = next;
    }
    if cost[dst as usize] == 9223372036854775807 {
        -1
    } else {
        cost[dst as usize]
    }
}

fn get_min(a: isize, b: isize) -> isize {
    if a < b {
        a
    } else {
        b
    }
}

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_02_3_week/Code01_CheapestFlightsWithinKStops.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-04-28,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档