787. Cheapest Flights Within K Stops

#### QUESTION:

There are n cities connected by m flights. Each flight 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.

Constraints:

``````The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 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.
``````

#### EXPLANATION:

1. k也就是edge必须是>0的
2. cost也必须必当前的cost小才行

1. 首先进行图的绘制： 创建hashmap数组，数组的index表示src，hashmap的key表示dst，而value表示price
2. 对当前的图进行dfs，src就是graph[i]就是对应的所有edge
3. 如果当前选择的edge超过了k那么就可以直接跳过这次
4. 如果当前src=dst，则说明到达了终点，可以对结果进行更新
5. 否则就继续进行dfs，如果当前的cost已经超过了给定的结果，那么就可以直接跳过，来节省算法复杂度

#### SOLUTION:

``````class Solution {
public int findCheapestPriceResult = Integer.MAX_VALUE;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
HashMap<Integer,Integer>[] graph = new HashMap[n];
for(int i = 0 ;i< flights.length;i++){
if(graph[flights[i][0]] == null) graph[flights[i][0]] = new HashMap<>();
HashMap<Integer,Integer> tmp = graph[flights[i][0]];
tmp.put(flights[i][1],flights[i][2]);
}
findCheapestPriceHelper(graph,src,dst,K+1,0);
return findCheapestPriceResult==Integer.MAX_VALUE?-1:findCheapestPriceResult;
}

public void findCheapestPriceHelper(HashMap<Integer,Integer>[] graph,int src, int dst, int K,int cost){
if(K<0) return;
if(src==dst) {
findCheapestPriceResult = Math.min(findCheapestPriceResult,cost);
return;
}
HashMap<Integer, Integer> map = graph[src];
if(map == null) return;
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
if(cost + entry.getValue() > findCheapestPriceResult) continue;
findCheapestPriceHelper(graph,entry.getKey(),dst,K-1,cost+entry.getValue());
}
}
}
``````