Within K stops 最短路径 Cheapest Flights Within K Stops

时间:2023-01-08 16:48:06

2018-09-19 22:34:28

问题描述:

Within K stops 最短路径 Cheapest Flights Within K Stops

问题求解:

本题是典型的最短路径的扩展题,可以使用Bellman Ford算法进行求解,需要注意的是在Bellman Ford算法的时候需要额外申请一个数组来保存变量。

    int inf = (int)1e9;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
// write your code here
int[] dist = new int[n];
Arrays.fill(dist, inf);
dist[src] = 0;
for (int i = 0; i <= K; i++) {
int[] prev = Arrays.copyOf(dist, n);
for (int[] e : flights) {
int from = e[0];
int to = e[1];
int w = e[2];
if (prev[to] > prev[from] + w) {
dist[to] = prev[from] + w;
}
}
}
return dist[dst] == inf ? -1 : dist[dst];
}

  

Within K stops 最短路径 Cheapest Flights Within K Stops的更多相关文章

  1. &lbrack;Swift&rsqb;LeetCode787&period; K 站中转内最便宜的航班 &vert; Cheapest Flights Within K Stops

    There are n cities connected by m flights. Each fight starts from city u and arrives at v with a pri ...

  2. &lbrack;LeetCode&rsqb; Cheapest Flights Within K Stops K次转机内的最便宜的航班

    There are n cities connected by m flights. Each fight starts from city u and arrives at v with a pri ...

  3. &lbrack;LeetCode&rsqb; 787&period; Cheapest Flights Within K Stops K次转机内的最便宜航班

    There are n cities connected by m flights. Each fight starts from city u and arrives at v with a pri ...

  4. 787&period; Cheapest Flights Within K Stops

    There are n cities connected by m flights. Each fight starts from city u and arrives at v with a pri ...

  5. LeetCode 787&period; Cheapest Flights Within K Stops

    原题链接在这里:https://leetcode.com/problems/cheapest-flights-within-k-stops/ 题目: There are n cities connec ...

  6. 【LeetCode】787&period; Cheapest Flights Within K Stops 解题报告(Python)

    作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 方法一:DFS 方法二:BFS 参考资料 日期 题目 ...

  7. &lbrack;LeetCode&rsqb; 787&period; Cheapest Flights Within K Stops&lowbar;Medium tag&colon; Dynamic Programming&comma; BFS&comma; Heap

    There are n cities connected by m flights. Each fight starts from city u and arrives at v with a pri ...

  8. K条最短路径算法&lpar;KSP&comma; k-shortest pathes&rpar;:Yen&&num;39&semi;s Algorithm

    参考: K最短路径算法之Yen's Algorithm Yen's algorithm 基于网络流量的SDN最短路径转发应用 K条最短路径算法:Yen's Algorithm 算法背景 K 最短路径问 ...

  9. 给定n,a求最大的k,使n!可以被a&Hat;k整除但不能被a&Hat;&lpar;k&plus;1&rpar;整除。

    题目描述: 给定n,a求最大的k,使n!可以被a^k整除但不能被a^(k+1)整除. 输入: 两个整数n(2<=n<=1000),a(2<=a<=1000) 输出: 一个整数. ...

随机推荐

  1. 基于java的分布式爬虫

    分类 分布式网络爬虫包含多个爬虫,每个爬虫需要完成的任务和单个的爬行器类似,它们从互联网上下载网页,并把网页保存在本地的磁盘,从中抽取URL并沿着这些URL的指向继续爬行.由于并行爬行器需要分割下载任 ...

  2. 数据库 &&num;39&semi;MessageManage&&num;39&semi; 的事务日志已满。若要查明无法重用日志中的空间的原因,请参阅 sys&period;databases 中的 log&lowbar;reuse&lowbar;wait&lowbar;desc 列。

    提供两种办法:(SQL Server2008) 注意:建议使用第一种方法.第二种方法只是删除已有日志文件,日后还会继续生成. 第一种方法:清空日志. 1.打开企业管理器,直接在查询分析器里执行:(如果 ...

  3. nyoj 82 迷宫寻宝(二)

    http://acm.nyist.net/JudgeOnline/problem.php?pid=83 题目解法主要在于判断两线段是否相交,思路是穷举所有地图四周的点,其中每一个边界上的点和终点构成一 ...

  4. oracle 数据库导出数据

    cmd导出数据: exp  ZD_ZD_ZDWW/zdzd1402!@11.111.111.213/orcl file=c:\1234.dmp owner=ZD_ZD_ZDWW

  5. ArcGIS Portal 10&period;4 本地坐标系的web 3d地形展示制作说明

    原文:ArcGIS Portal 10.4 本地坐标系的web 3d地形展示制作说明 ArcGIS Portal 10.4 本地坐标系的web 3d地形展示制作说明 By 李远祥 ArcGIS Por ...

  6. supesite 模板相关文档记录

    文件说明:http://wenku.baidu.com/view/69c07820af45b307e87197ac.html 开发文档:http://wenku.baidu.com/view/35f6 ...

  7. Maven中聚合与集成的区别

    如test-parent是一个聚合工程,打包方式为pom.xml test-a是test-parent的一个moudle模块,打包方式为jar,并且继承自test-parent: test-b是tes ...

  8. IO流(3)—字节流

    IO体系: 抽象基类----节点流(文件流) InputStream--FileInputStream(字节流) OutputStream--FileOutputSteam(字节流) Reader - ...

  9. OpenGL学习(2)——绘制三角形

    在创建窗口的基础上,添加代码实现三角形的绘制. 声明和定义变量 在屏幕上绘制一个三角形需要的变量有: 三角形的三个顶点坐标: Vertex Buffer Object 将顶点数据存储在GPU的内存中: ...

  10. jQuery-处理class属性

    1.addClass方法 为每个匹配的元素添加指定的样式类名 参数类型说明: 1)class名称(字符串) 每个匹配元素添加的一个或多个用空格隔开的样式名 2)function(index, curr ...