CheapestFlightsWithinKStops [source code]
public class CheapestFlightsWithinKStops {
static
/******************************************************************************/
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
Map<Integer, List<Node>> edges = new HashMap<> ();
for (int i = 0; i < flights.length; i++) {
int[] edge = flights[i];
edges.computeIfAbsent (edge[0], label -> new ArrayList<> ()).add (new Node (edge[1], edge[2]));
}
PriorityQueue<Node> pq = new PriorityQueue<> ((a, b) -> a.dist - b.dist);
int[][] dist = new int[n][k + 2];
for (int i = 0; i < dist.length; i++) for (int j = 0; j < dist[0].length; j++)
dist[i][j] = i == src ? 0 : Integer.MAX_VALUE;
pq.offer (new Node (src, 0));
while (!pq.isEmpty ()) {
Node cur_node = pq.poll ();
if (cur_node.label == dst)
break; // breaking out as soon as we meet DST is safe
if (edges.containsKey (cur_node.label)) {
for (Node neighbor : edges.get (cur_node.label)) {
int new_step = cur_node.step + 1, new_dist = cur_node.dist + neighbor.dist;
if (new_step <= k + 1 && new_dist < dist[neighbor.label][new_step]) {
dist[neighbor.label][new_step]= new_dist;
pq.offer (new Node (neighbor.label, new_dist, new_step));
}
}
}
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < dist[dst].length; i++)
res = Math.min (res, dist[dst][i]);
return res < Integer.MAX_VALUE ? res : -1;
}
static class Node {
int label;
int dist;
int step = 0;
Node (int l, int d) {label = l; dist = d; }
Node (int l, int d, int s) {label = l; dist = d; step = s; }
public String toString () {
return String.format ("[%d, %d, %d]", label, dist, step);
}
}
}
/******************************************************************************/
public static void main(String[] args) {
CheapestFlightsWithinKStops.Solution tester = new CheapestFlightsWithinKStops.Solution();
int[][][] inputs = {
{{0,1,100},{1,2,100},{0,2,500}}, {{3,0,2,1}},{{200}},
{{0,1,100},{1,2,100},{0,2,500}}, {{3,0,2,0}}, {{500}},
{{0,1,2}}, {{2,1,0,0}}, {{-1}},
{{0,1,5},{1,2,5},{0,3,2},{3,1,2},{1,4,1},{4,2,1}}, {{5,0,2,2}}, {{7}},
};
for (int i = 0; i < inputs.length / 3; i++) {
System.out.println (Printer.separator ());
int[][] flights = inputs[3 * i];
int[] ar = inputs[3 * i + 1][0];
int n = ar[0], src = ar[1], dst = ar[2], k = ar[3], ans = inputs[3 * i + 2][0][0], output = tester.findCheapestPrice (n, flights, src, dst, k);
System.out.printf ("%s and %s -> %s, expected: %d\n",
Matrix.printMatrix (flights), Printer.array (ar), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
感觉是DJ算法的变形, 正好从来没有写过这个算法, 这次实现一下;
算是一个对PriorityQueue解法的介绍的比较好的;
https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/
The time complexity remains O(ELogV)) as there will be at most O(E) vertices in priority queue and O(Log E) is same as O(Log V)
还有一个matrix解法:
https://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
复杂度差一点, 但是写法也很好;
最后直接用跑PriorityQueue的做法完成了, 果然是正确的; 注意, 除了PriorityQueue里面的node自己要维护dist, 外面还要用一个dist数组来维护真正的min disttance to each node, 因为我们这个PriorityQueue做法, 在PriorityQueue里面可能会有过期的copy of node, 所以PriorityQueue里面的distance是不够准确的;
另外, 为什么一个worse的node(distance更大)不会造成影响? 因为他被pop出来之后, 直接会检查自己的所有neighbor, 然后发现自己无法改变他们(因为有一个更好的copy已经更新过他们了, 注意, 更新的时候比对的是dist数组的finalized distance, 而不是PriorityQueue里面翻出来的), 所以这个worse copy直接pop完了之后什么也没有做就消失了;
geeks4geeks讲这些东西就真的讲的不错; 之前在一个乱七八糟的网站也看到过一个用PriorityQueue的实现DJ算法, 但是那个写的相当啰嗦;
geeks4geeks还有自己实现heap的做法, 不过这个就比较偏门了, 暂时不看; 太难的solution, 真正面试你写出来未必都会对你有很大帮助, 地里也看到了, 有可能面试官看不懂比他记住的答案更好的答案, 就认为你是错的; 当然, 这也告诫你, 解释和交流也很重要, 如果你能解释清楚, 也就不会发生这种问题了; 如果知道一个很好的解法但是不知道为什么, 讲不出来, 反而更加危险;
发帖之后, 原来的这个算法:
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
Map<Integer, List<Node>> edges = new HashMap<> ();
for (int i = 0; i < flights.length; i++) {
int[] edge = flights[i];
edges.computeIfAbsent (edge[0], label -> new ArrayList<> ()).add (new Node (edge[1], edge[2]));
}
PriorityQueue<Node> pq = new PriorityQueue<> ((a, b) -> a.dist - b.dist);
int[] dist = new int[n];
Arrays.fill (dist, Integer.MAX_VALUE);
dist[src] = 0;
pq.offer (new Node (src, 0));
while (!pq.isEmpty ()) {
Node cur_node = pq.poll ();
if (cur_node.label == dst)
break;
if (edges.containsKey (cur_node.label)) {
for (Node neighbor : edges.get (cur_node.label)) {
int new_dist = cur_node.dist + neighbor.dist;
if (new_dist < dist[neighbor.label] && cur_node.step + 1 <= k + 1) {
dist[neighbor.label] = new_dist;
Node new_neighbor = new Node (neighbor.label, new_dist);
new_neighbor.step = cur_node.step + 1;
pq.offer (new_neighbor);
}
}
}
}
return dist[dst] < Integer.MAX_VALUE ? dist[dst] : -1;
}
static class Node {
int label;
int dist;
int step = 0;
Node (int l, int d) {label = l; dist = d; }
public String toString () {
return String.format ("[%d, %d]", label, dist);
}
}
}
这个居然被这个test一个提出的test4给break了:
然后改成了:
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
Map<Integer, List<Node>> edges = new HashMap<> ();
for (int i = 0; i < flights.length; i++) {
int[] edge = flights[i];
edges.computeIfAbsent (edge[0], label -> new ArrayList<> ()).add (new Node (edge[1], edge[2]));
}
PriorityQueue<Node> pq = new PriorityQueue<> ((a, b) -> a.dist - b.dist);
int min_dist_dst = Integer.MAX_VALUE;
pq.offer (new Node (src, 0));
while (!pq.isEmpty ()) {
System.out.printf ("pq: %s, min_dist_dst: %d\n", pq, min_dist_dst);///
Node cur_node = pq.poll ();
if (cur_node.label == dst)
min_dist_dst = Math.min (min_dist_dst, cur_node.dist);
if (edges.containsKey (cur_node.label)) {
for (Node neighbor : edges.get (cur_node.label)) {
if (cur_node.step + 1 <= k + 1) {
Node new_neighbor = new Node (neighbor.label, cur_node.dist + neighbor.dist);
new_neighbor.step = cur_node.step + 1;
pq.offer (new_neighbor);
}
}
}
}
return min_dist_dst < Integer.MAX_VALUE ? min_dist_dst : -1;
}
static class Node {
int label;
int dist;
int step = 0;
Node (int l, int d) {label = l; dist = d; }
public String toString () {
return String.format ("[%d, %d, %d]", label, dist, step);
}
}
}
但是这个就TLE了; 这个是因为虽然这里用了PriorityQueue, 但是实际上根本没有利用PriorityQueue本身的性质, 最后这个浪费在维护PriorityQueue上的时间就过来捣乱了;
所以最后这个题目最正确的办法估计还是BFS;
改了半天总算是改好了; 但是现在这个版本, PriorityQueue换成普通的queue居然就不行了, 不知道为什么, 因为我感觉这个算法到现在来说, 你先Poll哪个还有关系吗?
速度是145ms (NA);
本来的版本, 是没有上面的comment那里的break的; 看了editorial之后, 发现是可以第一次看到dst就立刻break的; 速度也变成了94ms;
editorial
Approach #1: Maintain Cheapest To Target [Accepted]
Intuition and Algorithm
Say pre[node] is the smallest distance to that node within T stops. Let's try to find the smallest distance dis[node] to that node within T+1 rounds. For every edge in flights that connects places u and v with cost w, the new distance would be dis[v] = min(dis[v], pre[u] + w).
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
int[] dis = new int[n];
int[] pre = new int[n];
Arrays.fill(dis, Integer.MAX_VALUE / 2);
Arrays.fill(pre, Integer.MAX_VALUE / 2);
dis[src] = pre[src] = 0;
for (int i = 0; i <= K; ++i) {
for (int[] edge: flights)
dis[edge[1]] = Math.min(dis[edge[1]], pre[edge[0]] + edge[2]);
pre = dis;
}
return dis[dst] < Integer.MAX_VALUE / 2 ? dis[dst] : -1;
}
}
空间优化之后的DP做法, 时间复杂度是O(EK);
Approach #2: Dijkstra's [Accepted]
Intuition
Instead of nodes being places, use places and number of stops. We want to find the lowest cost from source to target, which makes Dijkstra's a good candidate algorithm.
If we continually extend our potential flightpaths in order of cost, we know once we've reached the destination dst that it was the lowest cost way to get there. This is the idea behind Dijkstra's algorithm.
Algorithm
Dijkstra's algorithm uses a priority queue to continually search the next node with the lowest cost.
If we've come to a node and it has a lower recorded cost or we've taken too many steps, we don't need to search it. If we reach our destination, because we are searching in order of lowest cost first, it must have the lowest cost.
Otherwise, for every outbound flight from node that is better, we'll add it to our priority queue of things to search.
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
int[][] graph = new int[n][n];
for (int[] flight: flights)
graph[flight[0]][flight[1]] = flight[2];
Map<int[], Integer> best = new HashMap();
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, 0, src});
while (!pq.isEmpty()) {
int[] info = pq.poll();
int cost = info[0], k = info[1], place = info[2];
if (k > K+1 || cost > best.getOrDefault(new int[]{k, place}, Integer.MAX_VALUE))
continue;
if (place == dst)
return cost;
for (int nei = 0; nei < n; ++nei) if (graph[place][nei] > 0) {
int newcost = cost + graph[place][nei];
if (newcost < best.getOrDefault(new int[]{k+1, nei}, Integer.MAX_VALUE)) {
pq.offer(new int[]{newcost, k+1, nei});
best.put(new int[]{k+1, nei}, newcost);
}
}
}
return -1;
}
}
复杂度O(E + NlogN);
砍了他这个方法之后, 我给我自己的方法也加了一个break: 看到dst就立刻退出; 这个可以成功是因为我实际上是一个向后填表的DP做法, 所以当我们第一次到dst的时候, 一定是之前有某一个parent成功的relax了, 也就代表这是一个最优解; 无论这个最优path是多少step的, 反正是第一个到达的;
参考他的方法, 对我自己的代码进一步优化:
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
Map<Integer, List<Node>> edges = new HashMap<> ();
for (int i = 0; i < flights.length; i++) {
int[] edge = flights[i];
edges.computeIfAbsent (edge[0], label -> new ArrayList<> ()).add (new Node (edge[1], edge[2]));
}
PriorityQueue<Node> pq = new PriorityQueue<> ((a, b) -> a.dist - b.dist);
int[][] dist = new int[n][k + 2];
for (int i = 0; i < dist.length; i++) for (int j = 0; j < dist[0].length; j++)
dist[i][j] = i == src ? 0 : Integer.MAX_VALUE;
pq.offer (new Node (src, 0));
while (!pq.isEmpty ()) {
Node cur_node = pq.poll ();
if (cur_node.label == dst)
return cur_node.dist;
if (edges.containsKey (cur_node.label)) {
for (Node neighbor : edges.get (cur_node.label)) {
int new_step = cur_node.step + 1, new_dist = cur_node.dist + neighbor.dist;
if (new_step <= k + 1 && new_dist < dist[neighbor.label][new_step]) {
dist[neighbor.label][new_step]= new_dist;
pq.offer (new Node (neighbor.label, new_dist, new_step));
}
}
}
}
return -1;
}
static class Node {
int label;
int dist;
int step = 0;
Node (int l, int d) {label = l; dist = d; }
Node (int l, int d, int s) {label = l; dist = d; step = s; }
public String toString () {
return String.format ("[%d, %d, %d]", label, dist, step);
}
}
}
再回头看了一下他这里这个思路, 其实awice这个思路跟我的是差不多的, 他的best这个map, key实际上还是cost, label, 只不过他用HashMap来存放, 我直接一个二维数组;
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K)
{
const int INF = 1e9;
K++;
vector<vector<int>> ans(n, vector<int>(K+1));
for(int i = 0; i < n; i++)
{
for(int j = 0; j <= K; j++)
{
ans[i][j] = INF;
}
}
ans[src][0] = 0;
for(int i = 1; i <= K; i++)
{
for(int j = 0; j < n; j++)
ans[j][i] = ans[j][i-1];
for(const vector<int>& f: flights)
{
ans[f[1]][i] = min(ans[f[1]][i], ans[f[0]][i-1] + f[2]);
}
}
if(ans[dst][K] == INF) return -1;
return ans[dst][K];
}
};
总体思路还是很清晰的, 就是一个DP算法, 注意, 填表的时候要先K, 然后再N;
https://leetcode.com/problems/cheapest-flights-within-k-stops/discuss/115596/c++-8-line-bellman-ford
class Solution {
public:
//bellman ford.
//just run it k+1 iterations.
int findCheapestPrice(int n, vector<vector<int>>& a, int src, int sink, int k) {
vector<int> c(n, 1e8);
c[src] = 0;
for(int z=0; z<=k; z++){
vector<int> C(c);
for(auto e: a)
C[e[1]] = min(C[e[1]], c[e[0]] + e[2]);
c = C;
}
return c[sink] == 1e8 ? -1 : c[sink];
}
};
所以这个forward方向的类似DP的, 其实就是BF算法;
因为只需要查询上一个K的row, 所以是一个可以优化空间到linear的DP, 这里就是这个思路;
Many posts on the discussion here for this problem doesn’t produce valid output for this input:
4 [[0,1,100],[0,2,300],[0,3,500],[1,2,100],[2,3,100]] 0 3 1Because if you simply allow the BFS to run 2 iterations (with k = 1), the distance between 0 and 3 would reduce to 300 because of this path (0->1->2->3), we shouldn’t allow 2 to update 3 in the last iteration.If you write out what’s in the queue and manually run it you will see what I’m saying. The trick is to only allow updates for destination in the last iteration.
public class Solution
{
public int FindCheapestPrice(int n, int[,] flights, int src, int dst, int K) {
var nodes = this.InitializeGraph(flights);
var queue = new Queue<int>();
var cost = new Queue<int>();
foreach (var airport in nodes.Keys) {
nodes[airport].MinCost = Int32.MaxValue;
}
nodes[src].MinCost = 0;
queue.Enqueue(src);
cost.Enqueue(0);
int stops = 0;
while (queue.Count != 0) {
if (stops > K) {
break;
}
int size = queue.Count;
for (int i = 0; i < size; i++) {
var currentNode = nodes[queue.Dequeue()];
int currentCost = cost.Dequeue();
// Optional: If we reach destination, we don't need to process target's neighbor
if (currentNode.Label == dst) {
continue;
}
foreach (var neighbor in currentNode.Neighbors.Keys) {
// If this is the last iteration, we should only update neighbor == target
// otherwise we might create other minCost that require more than k stops
if (stops == K && neighbor != dst) {
continue;
}
int nextCost = currentCost + currentNode.Neighbors[neighbor];
if (nextCost < nodes[neighbor].MinCost) {
nodes[neighbor].MinCost = nextCost;
queue.Enqueue(neighbor);
cost.Enqueue(nextCost);
}
}
}
stops++;
}
if (nodes[dst].MinCost == Int32.MaxValue) {
return -1;
}
return nodes[dst].MinCost;
}
private Dictionary<int, Node> InitializeGraph(int[,] flights) {
var nodes = new Dictionary<int, Node>();
for(int f = 0; f < flights.GetLength(0); f++) {
var from = flights[f,0];
var to = flights[f, 1];
var cost = flights[f, 2];
if (!nodes.ContainsKey(from)) {
nodes[from] = new Node(from);
}
if (!nodes.ContainsKey(to)) {
nodes[to] = new Node(to);
}
nodes[from].Neighbors[to] = cost;
}
return nodes;
}
}
public class Node
{
public int Label { get; set; }
public Dictionary<int, int> Neighbors { get; }
public int MinCost { get; set; }
public Node(int label) {
this.Label = label;
this.Neighbors = new Dictionary<int, int>();
}
}
好像说的有点道理; 看起来BFS其实也是可以做的; 避免超时的办法就是即使的停止;
大概看了一下意思, 没有仔细看了;
submission基本没有;
Problem Description
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 fights, 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 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.
Difficulty:Medium
Total Accepted:385
Total Submissions:1.5K
Contributor:1337c0d3r