Minimum Score of a Path Between Two Cities - 2492

PHOTO

Wed Mar 22 2023 16:34:51 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07

class Solution {
    public int minScore(int n, int[][] roads) {
        /*question of connected components , find 1's component and find minimum edge 
        weight in 1's component as we have to find path between 1 and n
        */

        //making adjency list
        HashMap<Integer, ArrayList<List<Integer>>> map = new HashMap<>();

        for(int[] road : roads){

            map.computeIfAbsent(road[0],k -> new ArrayList<List<Integer>>()).add(Arrays.asList(road[1],road[2]));

            map.computeIfAbsent(road[1],k -> new ArrayList<List<Integer>>()).add(Arrays.asList(road[0],road[2]));
        }

        System.out.println(map);

        return BFS(n , map);
    }


    public int BFS(int n , HashMap<Integer, ArrayList<List<Integer>>> map){

        int ans = Integer.MAX_VALUE;
        Queue<Integer> q = new ArrayDeque<>();
        boolean visited[] = new boolean[n+1];
        
        //adding first node
        q.add(1);
        visited[1] = true;


        while(q.size()!=0){
            int node = q.poll();        //remove
            
            //work and then add into q
            //if(map.containsKey(node)==false) continue;

            for(List<Integer> edge : map.get(node)){
                ans = Math.min(ans , edge.get(1));

                if(visited[edge.get(0)]==false){
                    q.add(edge.get(0));
                    visited[edge.get(0)] = true;
                }
            }
            
        }

        return ans;
    }
}

https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities/description/

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

DP level 2

@Ayush_dabas07

Q66 Distinct Echo Substrings - LeetCode 1316 (rabin karp rolling hash -> O(n^2)) Q66 Distinct Echo Substrings - LeetCode 1316(O(n^3) solution) Q65 Interleaving String - LeetCode 97 Q64 Frog Jump - LeetCode 403 Q63 Champagne Tower - LeetCode 799 Q62 Super Ugly Number - LeetCode 313 Q61 Ugly Number 2 - LeetCode 264 Q60 Minimum Insertion Steps to Make a String Palindrome - LeetCode 1316 Q59 Temple Offerings | Practice | GeeksforGeeks Q58 Word Break - LeetCode 139 Q57 Arithmetic Slices II - Subsequence - LeetCode 446 Q56 Arithmetic Slices - LeetCode 413 Q55 Max sum of M non-overlapping subarrays of size K - GeeksforGeeks (tabulization) Q55 Max sum of M non-overlapping subarrays of size K - GeeksforGeeks (memoization) Q54 Maximum Sum of 3 Non-Overlapping Subarrays - LeetCode 689 Q53 Maximum Sum of Two Non-Overlapping Subarrays - LeetCode 1031 Q52 Maximum difference of zeros and ones in binary string | Practice | GeeksforGeeks Q51 Mobile numeric keypad | Practice | GeeksforGeeks Q50 Distinct Transformation LeetCode Playground ( tabulization approach) Q50 - Distinct Transformation- LeetCode Playground ( recursion + memoization approach) Q49 Highway BillBoards - Coding Ninjas Codestudio approach 2 Q49 Highway BillBoards - Coding Ninjas Codestudio (approach 1 LIS) Q48 Knight Probability in Chessboard - LeetCode 688 Q47 Cherry Pickup - LeetCode 741 (recursion approach) Q46 Super Egg Drop - LeetCode 887 Q45 Predict the Winner - LeetCode 486 Q45 Optimal Strategy For A Game | Practice | GeeksforGeeks | leetcode 46 Q44 Largest Sum Subarray of Size at least K | Practice | GeeksforGeeks Q42 Maximum Subarray - LeetCode 53 Q41 Minimum Cost To Make Two Strings Identical | Practice | GeeksforGeeks Q40 Minimum ASCII Delete Sum for Two Strings - LeetCode 712 Q39 Scramble String - LeetCode 87 Q38 Edit Distance - LeetCode 72 Q37 Regular Expression Matching - LeetCode 10 Q36 Wildcard Matching - LeetCode Q35 Longest Repeating Subsequence | Practice | GeeksforGeeks Q34 Longest Common Substring | Practice | GeeksforGeeks Q33 Count Different Palindromic Subsequences - LeetCode 730 Q32 Number of distinct subsequences | Practice | GeeksforGeeks Q31 Longest Palindromic Substring - LeetCode Q30 Count Palindromic Subsequences | Practice | GeeksforGeeks Q29 Longest Palindromic Subsequence - LeetCode 516 Q28 Longest Common Subsequence - LeetCode 1143 Q27 Minimum Score Triangulation of Polygon - LeetCode 1039 Q26 Optimal binary search tree | Practice | GeeksforGeeks Q24 Matrix Chain Multiplication | Practice | GeeksforGeeks Q23 Palindrome Partitioning II - LeetCode 132 Q23 Palindrome Partitioning II - LeetCode - 132 ( n^3 approach) Q22 Palindromic Substrings - LeetCode 647 Q21 Rod Cutting | Practice | GeeksforGeeks Q20 Minimum Score Triangulation of Polygon - LeetCode 1039 Q19 Intersecting Chords in a Circle | Interviewbit Q18 Generate Parentheses - LeetCode 22 Q17 PepCoding | Count Of Valleys And Mountains Q16 Unique Binary Search Trees - LeetCode 96 Q15 Catalan Number Minimum Score of a Path Between Two Cities - 2492 Q14 Perfect Squares - LeetCode Q13 Russian Doll Envelopes - LeetCode (LIS in NlogN - accepted solution) Q13 Russian Doll Envelopes - LeetCode 354 solution1(LIS in O(n^2)) Q12 PepCoding | Maximum Non-overlapping Bridges Q11 Longest Bitonic subsequence | Practice | GeeksforGeeks Q10 Maximum sum increasing subsequence | Practice | GeeksforGeeks Q9 PepCoding | Print All Longest Increasing Subsequences Q8 Longest Increasing Subsequence - LeetCode 300 Q7 2 Keys Keyboard - LeetCode 650 Q-6 PepCoding | Print All Results In 0-1 Knapsack Q5 PepCoding | Print All Paths With Target Sum Subset Q4 PepCoding | Print All Paths With Maximum Gold Q3 PepCoding | Print All Paths With Minimum Cost Q2 Jump Game II - LeetCode 45 Q1 Maximal Square - LeetCode 221 Q67 Longest Increasing Subsequence - LeetCode 300 ( LIS O(nlogn) solution) Q43 K-Concatenation Maximum Sum - LeetCode 1191 Q13 Russian Doll Envelopes - LeetCode 354 ( LIS -> O(nlogn) solution) Q25 Burst Balloons - LeetCode 312

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 >>