站长工具

【力扣】787. K 站中转内最便宜的航班加权——有向图最短路径

作者：dotJunz

前言

我感觉这题比较有代表性，所以记录一下，这题是加权有向图中求最短路径的问题。

题目

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

动态规划

假设有一条路径是[src, i, ..., j, dst]，解法一子问题的定义是[src, i, ..., j]，解法二子问题的定义是[i, ..., j, dst]。

解法一需要知道哪些节点指向dst，需要求入度。
解法二需要知道src指向哪些节点，需要求出度。

解法一

如下图所示，想要求src到dst的最短路径，如果知道了src到s1和src到s2的最短路径，那么问题就好解决了。
在这里插入图片描述
加上s1和s2到dst的花费取最小值即可，伪代码如下

minPrice(dst, k) =
	min(minPrice(s1, k - 1) + w1, 
		minPrice(s2, k - 1) + w2)

最终代码

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];
    }
}

解法二

如下图所示，想要求src到dst的最短路径，如果知道了s1到dst和s2到dst的最短路径，那么问题就好解决了。

在这里插入图片描述
加上src到s1和s2的花费取最小值即可，伪代码如下

minPrice(src, k) =
	min(minPrice(s1, k - 1) + w1, 
		minPrice(s2, k - 1) + w2)

最终代码

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];
    }
}

小结

两种解法代码非常相似，具有对称性。对于有向图最短路径问题，常规思路都是 Dijkstra 等图论经典算法，没想到动态规划也可以，很奇妙。这也是我想记录这道题的原因吧。

BFS 算法思路

Dijkstra 算法

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});
    }

    // 启动 dijkstra 算法
    // 计算以 src 为起点在 k 次中转到达 dst 的最短路径
    K++;
    return dijkstra(graph, src, K, dst);
}

class State {
    // 图节点的 id
    int id;
    // 从 src 节点到当前节点的花费
    int costFromSrc;
    // 从 src 节点到当前节点经过的节点个数
    int nodeNumFromSrc;

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

// 输入一个起点 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;
}

参考资料

旅游省钱大法：加权最短路径

本文转载于网络 如有侵权请联系删除

相关文章

  • 聊聊golang的类型断言

    序本文主要研究一下golang的类型断言类型断言x.(T) 复制断言x不为nil且x为T类型如果T不是接口类型，则该断言x为T类型如果T类接口类型，则该断言x实现了T接口实例1funcmain(){ varxinterface{}=7 i:=x.(int) fmt.Println(reflect.TypeOf(i)) j:=x.(int32) fmt.Println(j) } 复制直接赋值的方式，如果断言为true则返回该类型的值，如果断言为false则产生runtimepanic；j这里赋值直接panic输出int panic:interfaceconversion:interface{}isint,notint32 goroutine1[running]: main.main() type_assertion.go:12+0xda exitstatus2 复制不过一般为了避免panic，通过使用ok的方式funcmain(){ varxinterface{}=7 j,ok:=x.(int32) ifok{ fmt.Println(reflect.TypeOf(j)) }else{

  • Spring MVC 函数式编程进阶

    1.前言上一篇对SpringMVC的函数式接口编程进行了简单入门，让很多不知道的同学见识了这种新操作。也有反应这种看起来没有传统写法顺眼，其实大家都一样。但是我们还是要敢于接受和尝试新事物。JavaLambada刚出来也是被人各种吐槽，现在我在很多项目都见到了它的身影。好了转回正题，本文是对上一篇的延伸，我们继续对FunctionalEndpoint进行一些了解和运用。范式转换其实上一篇已经介绍差不多了，但是一旦你初次接触这种方式往往会面临新的问题。2.新的问题在使用这种风格时我们也会遇到一些新的问题。接下来我们将通过举例来一步步解决这些问题。2.1如何异常处理接口异常处理是必须的。改成函数式风格后异常可以这样处理：/** *接口附带异常处理逻辑. * *@paramuserServicetheuserservice *@returntheuserbynamewitherrorhandle */ publicRouterFunction<ServerResponse>withErrorHandle(){ returnRouterFunctions.route() .GET(

  • 洞见技术的未来——最新期技术雷达即将发布！

    ThoughtWorks每年都会出品两期技术雷达，这是一份关于技术趋势的报告，比那些我们能在市面上见到的其他技术行情和预测报告更加具体、更具可操作性，因为它不仅涉及到新技术大趋势，更有细致到类库和工具的推荐和评论，因此更容易落地。经过半年的追踪与沉淀，ThoughtWorksTAB（ThoughtWorks技术咨询委员会）根据我们在多个行业中的实践案例，为技术者产出了第十八期技术雷达，对百余个技术条目进行分析，阐述它们目前的成熟度，并提供了相应的技术选型建议。本文将分享本期雷达的四大主题趋势，涵盖了目前最值得关注的物联网、云环境等技术领域（6月2日即将举办的技术雷达峰会中将就这几个主题进行分享）。浏览器增强，服务端式微为了实现应用逻辑，浏览器在持续扩展成为部署目标的能力。当平台能照顾好横切关注点和非功能性需求的同时，我们注意到后端逻辑的复杂性有逐步降低的趋势。WebAssembly的引入为web应用创建逻辑提供了新的语言选择，同时把处理过程更加推向金属侧（以及GPU）。WebBluetooth让浏览器能够处理那些原本是本地应用才能处理的功能，而且我们看到越来越多像CSSGridLayo

  • 如何集成云层与本地存储

    云和本地存储正走向越来越紧密的整合，于是云成为了另一个存储管理员可用的层级。组织不大可能把100%的数据都移到云服务上，但大多数企业都会至少想让一部分数据能够利用云存储的优势。最好的方法是以混合的方式使用云存储来创建一个本地存储资源和云的无缝集成。这个云计算层的整合可以通过专用的软件，支持云的应用或者存储系统或云网关产品中内建的功能来达成。为什么要追逐云?今年恐怕将是公有云采纳终于超越开发项目和Web2.0公司，并堂堂正正的踏入IT主流的一年。云服务供应商可以提供在弹性、敏捷性、可扩展能力和效用定价等方面的巨大优势。当然，在安全性、竞争力、长期成本和性能方面仍然有着不可避免的担忧。以及，并不是所有的应用或工作负载都是云就绪的，还有大部分组织还无法完全在公有云上运营。不过，这些问题导致了我们今天在实际上所看到的混合云方式，试图将这两个世界的优点结合在一起。Taneja集团的研究支持这个看法，指出了现在的企业IT组织只有大约10%是考虑完全转移至公有云的。其他绝大多数的IT部门，至少在接下来的3到5年间，对未来架构的展望仍然是会由云和本地基础架构组成，以超融合产品来加强。然而，也就是在这些

  • 腾讯云云数据库MySQL查询实例基本信息api接口

    1.接口描述接口请求域名：cdb.tencentcloudapi.com。 查询实例基本信息（实例ID，实例名称，是否开通加密） 默认接口请求频率限制：20次/秒。 APIExplorer提供了在线调用、签名验证、SDK代码生成和快速检索接口等能力。您可查看每次调用的请求内容和返回结果以及自动生成SDK调用示例。 2.输入参数以下请求参数列表仅列出了接口请求参数和部分公共参数，完整公共参数列表见公共请求参数。 参数名称 必选 类型 描述 Action 是 String 公共参数，本接口取值：DescribeDBInstanceInfo。 Version 是 String 公共参数，本接口取值：2017-03-20。 Region 是 String 公共参数，详见产品支持的地域列表。 InstanceId 是 String 实例ID。 3.输出参数 参数名称 类型 描述 InstanceId String 实例ID。 InstanceName String 实例名称。 Encryption String 是否开通加密，YE

  • [财务][数据化分析][帆软]报表设计-聚合报表设计

     [财务][数据化分析][帆软]报表设计-聚合报表设计 1.聚合报表设计界面 聚合报表指一个报表中包含多个模块，每一块都类似一张单独的报表或者一张图表，块与块之间相对独立，互不影响。 聚合报表特点：空白画布式设计界面，每个模块相互独立，专门解决大报表难题，单元格扩展分离，互不影响。 同时聚合报表还存在一些不足：不支持自适应，单元格扩展分离但组件依旧相互推开 注：需要使用多个聚合块时，再拖动报表类型聚合块到模板设计界面就可以了。操作同上，多聚合块之间是没有影响的。 2.新建聚合报表 1)点击菜单文件>新建聚合报表，可以直接新建聚合报表，如下图： 2)新建普通报表的时候，添加sheet的时候可以添加普通报表及聚合报表 3)新建聚合报表的时候，添加sheet的时候只能添加聚合报表 3.导出聚合报表 想要导出聚合报表时，可以直接导出Excel/Word/PDF等格式，如下图： Web端也可以直接导出(Excel/Word/PDF)和打印(pdf/applet/flash)，如下图： 注1：JAR为2018.4.9及之后，不再支持applet打印，请使用其他打印

  • 一张图作为Python入门(图片来自网络)

  • java中的IO整理

    写在前面：本文章基本覆盖了javaIO的全部内容，java新IO没有涉及，因为我想和这个分开，以突出那个的重要性，新IO哪一篇文章还没有开始写，估计很快就能和大家见面。照旧，文章依旧以例子为主，因为讲解内容的java书很多了，我觉的学以致用才是真。代码是写出来的，不是看出来的。 最后欢迎大家提出意见和建议。 【案例1】创建一个新文件 1 2 3 4 5 6 7 8 9 10 11 import java.io.*; class hello{     public static void main(String[]args){         Filef=new File("D:\\hello.txt");         try{        

  • 第八章学习小结

    本章节学习了各种的排序方法，它们的性能比较如下：    1.直接插入排序 直接插入排序的核心思想就是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过。 voidInsertSort(intR[],intn) { inti,j,temp; for(i=1;i<n;i++)//插入排序共需要插入n个元素，但此处我们默认序列中存在R[0]这个元素，故之后需进行n-1次插入操作 { temp=R[i]; j=i-1; while(j>=0&&temp<R[j])//比插入元素大的元素进行后移操作 { R[j+1]=R[j]; --j; } R[j+1]=temp;//插入要插入的元素 } }复制   2.希尔排序 希尔排序的算法思想：将待排序数组按照步长进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。 3.简单选择排序     (1)从待

  • Linux下逻辑地址、线性地址、物理地址详细总结

    Linux下逻辑地址、线性地址、物理地址详细总结 一、逻辑地址转线性地址     机器语言指令中出现的内存地址，都是逻辑地址，需要转换成线性地址，再经过MMU(CPU中的内存管理单元)转换成物理地址才能够被访问到。 我们写个最简单的helloworld程序，用gcc编译，再反编译后会看到以下指令： mov  0x80495b0,%eax 复制代码 这里的内存地址0x80495b0就是一个逻辑地址，必须加上隐含的DS数据段的基地址，才能构成线性地址。也就是说0x80495b0是当前任务的DS数据段内的偏移。  在x86保护模式下，段的信息（段基线性地址、长度、权限等）即段描述符占8个字节，段信息无法直接存放在段寄存器中（段寄存器只有2字节）。Intel的设计是段描述符集中存放在GDT或LDT中，而段寄存器存放的是段描述符在GDT或LDT内的索引值(index)。Linux中逻辑地址等于线性地址。为什么这么说呢？因为Linux所有的段（用户代码段、用户数据段、内核代码段、内核数据段）的线性

  • Mac OS 下包管理器 homebrew的安装

    homebrew：熟悉macos的小伙伴们一定都知道这个包管理工具，它非常方便且好用,安装它只需要打开终端并将以下代码粘贴到终端中运行即可: /usr/bin/ruby-e"$(curl-fsSLhttps://raw.githubusercontent.com/Homebrew/install/master/install)"复制    安装完成后可以使用如下命令:      1.安装你所需要的包： #brewinstall你所需要的包的名称 brewinstallwget复制      2.搜索你所需要的包： #brewsearch你所需要的包的名称 brewsearchwget复制      3.查看包的信息： #brewinfo你所需要的包的名称 brewinfowget复制      4.卸载指定包： #brewuninstall你所需要的包的名称 brewuninsta

  • javascript实现保留两位小数一位自动补零。

    functionreturnFloat(value){ varvalue=Math.round(parseFloat(value)*100)/100; varxsd=value.toString().split("."); if(xsd.length==1){ value=value.toString()+".00"; returnvalue; } if(xsd.length>1){ if(xsd[1].length<2){ value=value.toString()+"0"; } returnvalue; } } 复制   示例2： <script> tmp="1234567.57232" result=tmp.substr(0,tmp.indexOf(".")+3); alert(result); </script> 复制 　　

  • 运用离散化缩小不必要的范围+差分：只通过对两个区间的端点进行加减操作即可使这段区间上的元素得到加减

    原题链接：https://codeforces.com/gym/403650/problem/C      题目的原意是：给定n个区间，求1-1e9这个数轴上，对于每一个数点，在给定区间上出现过的最大值 一个最朴素的想法是：每给出一段区间，我们就让这个区间上代表的数num,count[num]++ 然后排个序，找到最大的count[x]; 但是会超时，而且num为1—1e9，没有那个数组能开这么大      差分：https://www.cnblogs.com/cilinmengye/p/16325069.html 离散化常用的去重方法： 前提是：数组是用vector来装   于是我们离散化区间端点，使其被另一个数代替，但有对其使用差分有着相同的效果 1#include<iostream> 2#include<algorithm> 3#include<cstring> 4usingnamespacestd; 5typedefpair<int,int>PII; 6

  • 测试

    测试

  • Redis系列四（keepalived+lvs搭建负载均衡）

    　　 　　1.安装Keepalived(主备服务器都要安装) 　　10.8.80.218 主服务器 　　10.8.80.217 备服务器　　 　　10.8.80.200 虚拟IP $wgethttp://www.keepalived.org/software/keepalived-1.2.0.tar.gz$tar-zxvfkeepalived-1.2.0.tar.gz$cdkeepalived-1.2.0$./configure--prefix=/usr/local/keepalived$make&&makeinstall 　　文件Copy $cp/usr/local/keepalived/etc/rc.d/init.d/keepalived/etc/init.d/keepalived$cp/usr/local/keepalived/sbin/keepalived/usr/sbin/$cp/usr/local/keepalived/etc/sysconfig/keepalived/etc/sysconfig/$mkdir-p/etc/kee

  • element-ui中的表单座机电话验证

       这个联系电话中需要验证手机号码和座机电话。element-ui中的rules="required||phone"这个写法仅仅验证了必填和手机号码的规则。但是我还需要验证座机号码规则。 所有绑定一个phoneRule做验证。    在data里面定义一个phone（跟return同级，不是在return里面）    正则规则:moblie=/^1(3|4|5|6|7|8|9)\d{9}$/  tel=/^(0[0-9]{2,3}\-)([2-9][0-9]{4,7})+(\-[0-9]{1,4})?$/

  • 1、跨域问题

    昨天前台系统的首页左侧类目出现了问题，前台访问后台JS报错，这里主要是因为跨域的问题。     1.1、 什么是跨域问题？       l 1）什么是跨域？   http://www.a.com  è http://www.b.com       不同域名，是跨域   http://www.a.com  è http://www.a.com:8080 域名相同，端口不同，是跨域   http://a.a.com  è http://b.a.com  不同二级域名，是跨域   http://www.a.com  è http://www.a.com/api   同一域名的不同路径，不是跨域   可以看出来，以下情况都属于跨域

  • python接口自动化12-流量回放神器：mitmproxy(下)

    一、mitmproxy做扩展 比如接口用例信息收集，回放对比，安全测试都可以那么便可以通过：mitmdump-sxx.py 扩展可查阅中文文档：https://ptorch.com/docs/10/addons-overview 1、有需求将某些请求域名包含的，写入文档方便回放，或者入库等。 importtime importjson defdumps(txt,beaut=0): """json序列化：dict->json""" try: ifbeaut: txt=json.dumps(txt,sort_keys=True,indent=4,ensure_ascii=False) else: txt=json.dumps(txt,ensure_ascii=False) except: txt=txt returntxt defloads(txt): """json反序列化：json->dict""" try: txt=json.loads(txt,encoding='UTF-8') except: txt=txt returntxt defresponse(f

  • dict()函数

    dict()函数 描述 字典dict()函数用于创建一个新的字典，用法与Pyhon字典 update() 方法相似。 语法 dict()函数函数语法： dict(key/value)复制 参数 key/value--用于创建字典的键/值对,此处可以表示键/值对的方法有很多，请看实例。 返回值 返回一个新的字典。 实例 dict0=dict()#传一个空字典 print('dict0:',dict0) dict1=dict({'three':3,'four':4})#传一个字典 print('dict1:',dict1) dict2=dict(five=5,six=6)#传关键字 print('dict2:',dict2) dict3=dict([('seven',7),('eight',8)])#传一个包含一个或多个元祖的列表 print('dict3:',dict3) dict5=dict(zip(['eleven','twelve'],[11,12]))#传一个zip()函数 print('dict5:',dict5)复制 以上实例输出结果为

  • sql with as 用法-Z

      以下内容转自：http://wudataoge.blog.163.com/blog/static/80073886200961652022389/ 一．WITHAS的含义 WITHAS短语，也叫做子查询部分（subqueryfactoring），可以让你做很多事情，定义一个SQL片断，该SQL片断会被整个SQL语句所用到。有的时候，是为了让SQL语句的可读性更高些，也有可能是在UNIONALL的不同部分，作为提供数据的部分。 特别对于UNIONALL比较有用。因为UNIONALL的每个部分可能相同，但是如果每个部分都去执行一遍的话，则成本太高，所以可以使用WITHAS短语，则只要执行一遍即可。如果WITHAS短语所定义的表名被调用两次以上，则优化器会自动将WITHAS短语所获取的数据放入一个TEMP表里，如果只是被调用一次，则不会。而提示materialize则是强制将WITHAS短语里的数据放入一个全局临时表里。很多查询通过这种方法都可以提高速度。 二．使用方法 先看下面一个嵌套的查询语句： select*fromperson.StateProvincewhere

  • 从头搭建Openstack运行环境（八）总结与未来计划

    通过前面七期的《从头搭建Openstack运行环境》一些列文章，我们讨论了为何要做从头搭建openstack运行环境、搭建的基础架构环境是什么和具体的计算网络相关的搭建步骤和顺序。这里面涉及了qemu、linuxbridge、openvswitch、iptables等等大量的基础概念。在平时的工作和学习中需要消化吸收。在我前阶段的openstack开发过程中，深深的感到对这些基本知识在openstack开发和运维中有着重要的作用。 一、前期我们主要涉及了一下几个方面： 1.项目与开发环境介绍 2.虚机配置与虚拟网络设备搭建 3.多租户虚机的创建  4.虚机安全组  5。虚机添加floatingip 6.虚机添加floatingip 7.租户网络间路由与防火墙 如果没看过前面章节的小伙伴可以翻阅此订阅号历史文章查看。   通过前期介绍的还只是些简单的场景，对于多租户多网络复杂场景还需要今后进一步详细去研究和测试。今后主要想在以下方面持续研究：   二、部署环境支持 1.KVM方向：增加KVM虚拟化环境部署流程，不再只是qemu虚拟化。 2.ceph

相关推荐

推荐阅读