Q25 Cheapest Flights Within K Stops - LeetCode 787

PHOTO

Fri Apr 28 2023 06:26:24 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        /* Q25 , bellman ford variation 
        -> We need to use another array temp so that the distances from the previous    
        iteration stored in dist don't change. 

        if we dont do that the array is going to dynamically change with each iteration of
        inside loop and we are not going to get ith edge answers .

        */

        //making path array 
        int[] path = new int[n];
        Arrays.fill(path , Integer.MAX_VALUE);
        path[src] = 0;  //cost of src from src = 0


        //firing bellman ford for K times so we just get <= k edges answer in the path
        for(int i = 0 ;i <= k ; i++){
            
            //copying path array so it doesn't get updated dynamically but stores one 
            // iteration result in the path array 
            int temp[] = Arrays.copyOf(path , n);
            for(int[] flight : flights) {
                int u = flight[0] , v = flight[1] , wt = flight[2];

                if(path[u] == Integer.MAX_VALUE)
                continue;

                temp[v] = Math.min(temp[v] , path[u] + wt);
            }
            path = temp;
        }

        //we didnt get any answer for <= k edges 
        return path[dst] == Integer.MAX_VALUE ? -1 : path[dst];
    }
}

https://leetcode.com/problems/cheapest-flights-within-k-stops/solutions/340911/Understanding-Bellman-Ford/

Save snippets that work from anywhere online with our extensions

Available in the Chrome Web Store

Get Firefox Add-on

Get VS Code extension

Comments

More like this

Graphs Level 2

@Ayush_dabas07

Minimum Score of a Path Between Two Cities - 2492 Number of Operations to Make Network Connected - 1319 Q42 Mother Vertex | Interviewbit (kosraju) Q41 Count Strongly Connected Components (Kosaraju’s Algorithm) Q40 Leetcode 734. Sentence Similarity Q39 Satisfiability of Equality Equations - LeetCode 990 Q38 Redundant Connection II - LeetCode 685 Q37 Redundant Connection - LeetCode 684 Q36 Minimize Malware Spread II - LeetCode 928 Q35 Minimize Malware Spread - LeetCode 924 Q34 Accounts Merge - LeetCode 721 Q33 Minimize Hamming Distance After Swap Operations - LeetCode 1722 Q32 Rank Transform of a Matrix - LeetCode 1632 Q32 Reconstruct Itinerary - leetcode 332 (eularian path && Eularian cycle) Q31 Regions Cut By Slashes - LeetCode 959 Q30 Minimum Spanning Tree | Practice | GeeksforGeeks (kruskal algo) Q29 Number of Islands II - Coding Ninjas (DSU) Q28 Remove Max Number of Edges to Keep Graph Fully Traversable - LeetCode 1579 Q27 Checking Existence of Edge Length Limited Paths - LeetCode 1675 Q26 Network Delay Time - LeetCode 743 Q25 Cheapest Flights Within K Stops - LeetCode 787 Q24 Distance from the Source (Bellman-Ford Algorithm) | Practice | GeeksforGeeks Q23 Connecting Cities With Minimum Cost - Coding Ninjas Q22 Swim in Rising Water - LeetCode 778 Q21 Water Supply In A Village - Coding Ninjas Q20 Minimum Spanning Tree | Practice | GeeksforGeeks(prims algo) Q19 Alien Dictionary | Practice | GeeksforGeeks Q18 Course Schedule - LeetCode 207 (kahn's algorithm) Q17 Minimum edges(0-1 BFS) | Practice | GeeksforGeeks Q17 Minimum edges(0-1 BFS) | Practice | GeeksforGeeks ( using djikstra) Q16 Sliding Puzzle - LeetCode 773 Q15 Bus Routes - LeetCode 815 Q14 Shortest Bridge - LeetCode 934 (without pair class) Q14 Shortest Bridge - LeetCode 934 ( with pair class) Q 13 As Far from Land as Possible - LeetCode 1120 Q12 Rotting Oranges - LeetCode 994 Q11 01 Matrix - LeetCode 542 Q10 Number of Distinct Islands | Practice | GeeksforGeeks Q9 Number of Enclaves - LeetCode 1085 Q8 Coloring A Border - LeetCode 1034 Q7 Unique Paths II - 63 Q6 Unique Paths III - LeetCode 980 Q5 Number of Provinces - LeetCode 547 Q4 Number of Islands - LeetCode 200 Q3 Number of Operations to Make Network Connected - LeetCode 1319 Q2 All Paths From Source to Target - LeetCode 797 Q1 Find if Path Exists in Graph - LeetCode 1971 Q43 is Cycle present in DAG ? GFG ( Topological Sort) Q43 is cycle present in DAG ? GFG (using kahns algo) Q44 Bellman ford | GFG ( Smaller code) Q45 Minimum Cost to Make at Least One Valid Path in a Grid - LeetCode 1368

Browse more snippets >>