787. Cheapest Flights Within K Stops
2024-10-19 06:20:15
There are n
cities connected by m
flights. Each fight starts from city u
and arrives at v
with a price w
.
Now given all the cities and flights, together with starting city src
and the destination dst
, your task is to find the cheapest price from src
to dst
with up to k
stops. If there is no such route, output -1
.
Example 1:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph looks like this:
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
Example 2:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph looks like this:
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.
Note:
- The number of nodes
n
will be in range[1, 100]
, with nodes labeled from0
ton
- 1
. - The size of
flights
will be in range[0, n * (n - 1) / 2]
. - The format of each flight will be
(src,
dst
, price)
. - The price of each flight will be in the range
[1, 10000]
. k
is in the range of[0, n - 1]
.- There will not be any duplicated flights or self cycles.
Approach #1: C++. []DFS
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
unordered_map<int, vector<pair<int, int>>> graph;
for (auto flight : flights) {
int s = flight[0], e = flight[1], p = flight[2];
graph[s].push_back(make_pair(e, p));
}
unordered_set<int> seen;
dfs(graph, seen, src, dst, K, 0, 0);
return ans == INT_MAX ? -1 : ans;
} void dfs(unordered_map<int, vector<pair<int, int>>>& graph, unordered_set<int> seen, int src, int dst, int K, int t, int p) {
if (t > K+1) return ;
if (src == dst) {
ans = p;
return ;
} seen.insert(src); for (auto v : graph[src])
if (!seen.count(v.first) && p + v.second < ans)
dfs(graph, seen, v.first, dst, K, t+1, p+v.second); } private:
int ans = INT_MAX; };
Analysis:
In this solution, The important point is p + v.second < ans.
最新文章
- Windows下用tree命令生成目录树
- iOS单例详解
- MaxTemperature程序Mapper ClassNotFoundException
- Flink 1.1 &ndash; ResourceManager
- Python数据库备份脚本
- IO复用(Reactor模式和Preactor模式)——用epoll来提高服务器并发能力
- 常用的十大Python开发工具
- vue中组件的四种方法总结
- Linux-fdisk磁盘分区命令(16)
- 异常-----The superclass ";javax.servlet.http.HttpServlet"; was not found on the Java Build Path。
- CSS速查列表-1-(background)背景
- SSH深度历险(七) 剖析SSH核心原理(一)
- latex数学公式笔记
- sort.go
- win10环境下适应pip安装autobahn提示认证失败的问题
- Bootstraptable源码
- c++ 异常 discards qualifiers 丢弃
- 让.Net程序支持命令行启动
- unity WegGL 调用js
- 得到类所在的jar包路径
热门文章
- apache配置详解 apache安装路径
- (转)C#用Linq实现DataTable的Group by数据统计
- SpringBoot自动化配置之四:SpringBoot 之Starter(自动配置)、Command-line runners
- IIS:template
- Cypress USB3014 controlEndPoint 使用事项
- PHP函数(六)-匿名函数(闭包函数)
- spring Annotation
- docker 笔记 (6)搭建本地registry
- 配置镜像yum源--解决RHN not available的问题
- VMware Workstation 软件 创建 Ubuntu 14.04虚拟机