Cheapest Flights Within K Stops


@awice. Thanks for your article. I am confused about the use of HashMap in Approach #2: Dijkstra's.
I tested the code snippet below:Map<int[], Integer> map = new HashMap<>(); map.put(new int[] {1,2}, 1); System.out.print(map.get(new int[] {1,2}));
The result is null
. In this case, if the key is an int[] array, HashMap doesn't work.
Could you please explain a bit about how your HashMap<int[ ], Integer> work in this solution?
Thank you.


@robinlzl1989 said in Cheapest Flights Within K Stops:
For Approch 1, the pre and dis array would be updated together because of the sentence "pre = dis", I don't think it is correct, even it could pass the test cases. Since two different rounds would interfere with each other.
Right, this caused the @ccwei 's test case to fail. The line should be replaced with
System.arraycopy(dis, 0 , pre, 0, n);


I like to point out that Approach 1 is essentially a modified BellmanFord Algorithm with two differences. First, the original BellmanFord does the same kind of relaxation for all edges for n  1 rounds, and this modified version K + 1 rounds. Second, the original BellmanFord use one array to keep track of the estimate of the distance of all nodes from source, and so at the round i of relaxation, the number of stops of the path reaching the some nodes may be far greater than i. This version use two arrays pre and dis to make sure that after i round of relaxation, the number of stops in the cheapest path reaching every nodes is less than i.

@awice I'm surprised you used int[] as the key and got accepted. Can you explain why does it work? To my knowledge an int array should not work as the key for a map since it doesn't override equals() and hashcode(). Thanks.

After review, Approach 1 was incorrect in how it handled copying over the previous array: using the shallow copy "pre = dis" had unintended side effects that were not caught by previous test cases. The actual idea of the algorithm was still valid. The approach has been modified slightly to now use dist[i&1] and dist[~i&1] as the two rows "dis" and "pre", which is accepted. Thanks everyone for the feedback.

@xxj79 Actually, I was mistaken  it doesn't work. I replaced the algorithm with a simple encoding of the tuple into an integer.

@brendon4565 said in Cheapest Flights Within K Stops:
I'm confused about the complexity analysis of approach 2. How does the algorithm prevent trying all possible (place, #stop) pairings?
Same question. I believe the runtime should be K(E + n * log(Kn)), ignoring the graph matrix initialization

Also, for solution 2, the hashmap can be replaced by a set, since the priority queue would always pop the costs in increasing order, so the new costs would never be smaller than previously seen costs of the same k value. The modified code is AC'ed
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]; Set<Integer> best = new HashSet(); 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]; int key = k * 1000 + place; if (k > K+1  best.contains(key)) continue; best.add(key); if (place == dst) return cost; for (int nei = 0; nei < n; ++nei) if (graph[place][nei] > 0) { if (!best.contains((k+1) * 1000 + nei)) { int newcost = cost + graph[place][nei]; pq.offer(new int[]{newcost, k+1, nei}); } } } return 1; }
}