2018-09-19 22:34:28
问题描述:
问题求解:
本题是典型的最短路径的扩展题,可以使用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的更多相关文章
-
[Swift]LeetCode787. K 站中转内最便宜的航班 | 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 ...
-
[LeetCode] 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 ...
-
[LeetCode] 787. 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 ...
-
787. 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 ...
-
LeetCode 787. Cheapest Flights Within K Stops
原题链接在这里:https://leetcode.com/problems/cheapest-flights-within-k-stops/ 题目: There are n cities connec ...
-
【LeetCode】787. Cheapest Flights Within K Stops 解题报告(Python)
作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 方法一:DFS 方法二:BFS 参考资料 日期 题目 ...
-
[LeetCode] 787. Cheapest Flights Within K Stops_Medium tag: Dynamic Programming, BFS, Heap
There are n cities connected by m flights. Each fight starts from city u and arrives at v with a pri ...
-
K条最短路径算法(KSP, k-shortest pathes):Yen&#39;s Algorithm
参考: K最短路径算法之Yen's Algorithm Yen's algorithm 基于网络流量的SDN最短路径转发应用 K条最短路径算法:Yen's Algorithm 算法背景 K 最短路径问 ...
-
给定n,a求最大的k,使n!可以被a^k整除但不能被a^(k+1)整除。
题目描述: 给定n,a求最大的k,使n!可以被a^k整除但不能被a^(k+1)整除. 输入: 两个整数n(2<=n<=1000),a(2<=a<=1000) 输出: 一个整数. ...
随机推荐
-
基于java的分布式爬虫
分类 分布式网络爬虫包含多个爬虫,每个爬虫需要完成的任务和单个的爬行器类似,它们从互联网上下载网页,并把网页保存在本地的磁盘,从中抽取URL并沿着这些URL的指向继续爬行.由于并行爬行器需要分割下载任 ...
-
数据库 &#39;MessageManage&#39; 的事务日志已满。若要查明无法重用日志中的空间的原因,请参阅 sys.databases 中的 log_reuse_wait_desc 列。
提供两种办法:(SQL Server2008) 注意:建议使用第一种方法.第二种方法只是删除已有日志文件,日后还会继续生成. 第一种方法:清空日志. 1.打开企业管理器,直接在查询分析器里执行:(如果 ...
-
nyoj 82 迷宫寻宝(二)
http://acm.nyist.net/JudgeOnline/problem.php?pid=83 题目解法主要在于判断两线段是否相交,思路是穷举所有地图四周的点,其中每一个边界上的点和终点构成一 ...
-
oracle 数据库导出数据
cmd导出数据: exp ZD_ZD_ZDWW/zdzd1402!@11.111.111.213/orcl file=c:\1234.dmp owner=ZD_ZD_ZDWW
-
ArcGIS Portal 10.4 本地坐标系的web 3d地形展示制作说明
原文:ArcGIS Portal 10.4 本地坐标系的web 3d地形展示制作说明 ArcGIS Portal 10.4 本地坐标系的web 3d地形展示制作说明 By 李远祥 ArcGIS Por ...
-
supesite 模板相关文档记录
文件说明:http://wenku.baidu.com/view/69c07820af45b307e87197ac.html 开发文档:http://wenku.baidu.com/view/35f6 ...
-
Maven中聚合与集成的区别
如test-parent是一个聚合工程,打包方式为pom.xml test-a是test-parent的一个moudle模块,打包方式为jar,并且继承自test-parent: test-b是tes ...
-
IO流(3)—字节流
IO体系: 抽象基类----节点流(文件流) InputStream--FileInputStream(字节流) OutputStream--FileOutputSteam(字节流) Reader - ...
-
OpenGL学习(2)——绘制三角形
在创建窗口的基础上,添加代码实现三角形的绘制. 声明和定义变量 在屏幕上绘制一个三角形需要的变量有: 三角形的三个顶点坐标: Vertex Buffer Object 将顶点数据存储在GPU的内存中: ...
-
jQuery-处理class属性
1.addClass方法 为每个匹配的元素添加指定的样式类名 参数类型说明: 1)class名称(字符串) 每个匹配元素添加的一个或多个用空格隔开的样式名 2)function(index, curr ...