[Leetcode 787]中转K站内最便宜机票
2024-09-08 14:09:34
题目
n个城市,想求从src到dist的最廉价机票
有中转站数K的限制,即如果k=5,中转10次机票1000,中转5次机票2000,最后返回2000
There are n
cities connected by some number of flights. You are given an array flights
where flights[i] = [fromi, toi, pricei]
indicates that there is a flight from city fromi
to city toi
with cost pricei
.
You are also given three integers src
, dst
, and k
, return the cheapest price from src
to dst
with at most k
stops. If there is no such route, return -1
.
Example 1:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: The graph is shown.
The cheapest price from city0
to city2
with at most 1 stop costs 200, as marked red in the picture.
Example 2:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: The graph is shown.
The cheapest price from city0
to city2
with at most 0 stop costs 500, as marked blue in the picture.
Constraints:
1 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= fromi, toi < n
fromi != toi
1 <= pricei <= 104
- There will not be any multiple flights between two cities.
0 <= src, dst, k < n
src != dst
思路
和https://www.cnblogs.com/inku/p/15622556.html类似
这题多了一个stepCheck,check中转的次数
dijsktra+优先队列
代码
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int[][] adj=new int[n][n];
for(int[] flight_line:flights){
//flighr_line: {from,to,money}
adj[flight_line[0]][flight_line[1]]=flight_line[2];
} int[] cost=new int[n];
int[] stepCheck=new int[n];
Arrays.fill(cost,Integer.MAX_VALUE);
Arrays.fill(stepCheck,Integer.MAX_VALUE);
cost[src] = 0;
stepCheck[src] = 0; //int[] cur position,cost,stops
PriorityQueue<int[]> pq=new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1]-o2[1];
}
});
//pq.add(new int[]{0,0,1}); 错误!
pq.offer(new int[]{src, 0, 0});//起点不一定是0,本身不算中转 while (!pq.isEmpty()){
int[] curPos=pq.poll();
int curNode=curPos[0];
int curCost=curPos[1];
int curStop=curPos[2];
if(curNode==dst)
return curCost;
if(curStop==k+1)
continue; for(int i=0;i<n;i++){
//两地有机票
if(adj[curNode][i]>0){ int cost_try=adj[curNode][i]+curCost;
if(cost_try<cost[i]){
cost[i]=cost_try;
pq.offer(new int[]{i,cost_try,curStop+1});//便宜的情况,加入
}
else if(curStop<stepCheck[i]){
pq.offer(new int[]{i,cost_try,curStop+1});//没便宜,但站数更少的情况,也加入
}
stepCheck[i]=curStop;//本身不算stop
}
}
}
return cost[dst]==Integer.MAX_VALUE?-1:cost[dst];
}
}
疑问
else if(curStop<stepCheck[i]){
pq.offer(new int[]{i,cost_try,curStop+1});//没便宜,但站数更少的情况,也加入
}
没便宜(cost更多),但站数更少的情况下虽然加入了,但因优先队列是按cost排序,那岂不是永远取不到?它的意义?
A:取得到,先加进去再说。虽然当前cost多,但后面的cost可能极小,成为最终解的一部分
最新文章
- JS生成指定范围内的数组
- CentOS 6.8 LAMP 安装配置
- Css背景渐变
- Enable rsh on MAC OS with command line
- Struts+Hibernate+Spring实现用户登录功能
- Windows Azure Web Site (15) 取消Azure Web Site默认的IIS ARR
- java 的方法注释写在哪里?
- Docker学习总结之docker入门
- J​a​v​a​S​c​r​i​p​t​针​对​D​o​m​相​关​的​优​化​心​得
- C#.net winform 控件和皮肤大全
- Bitmap介绍
- SQLServer分页
- ajaxSubmit提交文件表单不执行success
- C#里面Auotpostback回刷时候,textbox里面的password怎么保存
- rest api get 查询接口 多个参数
- Tp3.2提交表单与操作表单
- spring cloud 学习笔记(1)
- 20175303 Mycp实现Linux下cp xxx1 xxx2的功能
- Django积木块九——富文本编辑器
- python yield 关键字