Q17 Minimum edges(0-1 BFS) | Practice | GeeksforGeeks ( using djikstra)
Tue Apr 25 2023 06:19:02 GMT+0000 (Coordinated Universal Time)
Saved by @Ayush_dabas07
//{ Driver Code Starts import java.io.*; import java.util.*; class IntArray { public static int[] input(BufferedReader br, int n) throws IOException { String[] s = br.readLine().trim().split(" "); int[] a = new int[n]; for(int i = 0; i < n; i++) a[i] = Integer.parseInt(s[i]); return a; } public static void print(int[] a) { for(int e : a) System.out.print(e + " "); System.out.println(); } public static void print(ArrayList<Integer> a) { for(int e : a) System.out.print(e + " "); System.out.println(); } } class IntMatrix { public static int[][] input(BufferedReader br, int n, int m) throws IOException { int[][] mat = new int[n][]; for(int i = 0; i < n; i++) { String[] s = br.readLine().trim().split(" "); mat[i] = new int[s.length]; for(int j = 0; j < s.length; j++) mat[i][j] = Integer.parseInt(s[j]); } return mat; } public static void print(int[][] m) { for(var a : m) { for(int e : a) System.out.print(e + " "); System.out.println(); } } public static void print(ArrayList<ArrayList<Integer>> m) { for(var a : m) { for(int e : a) System.out.print(e + " "); System.out.println(); } } } class GFG { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t; t = Integer.parseInt(br.readLine()); while(t-- > 0){ int[] a = new int[2]; String s[] = br.readLine().trim().split(" "); if(s.length == 2){ a[0] = Integer.parseInt(s[0]); a[1] = Integer.parseInt(s[1]); } else{ a[0] = Integer.parseInt(s[0]); s = br.readLine().trim().split(" "); a[1] = Integer.parseInt(s[0]); } int[][] edges = IntMatrix.input(br, a[1], 2); int src; src = Integer.parseInt(br.readLine()); int dst; dst = Integer.parseInt(br.readLine()); Solution obj = new Solution(); int res = obj.minimumEdgeReversal(edges, a[0], a[1], src, dst); System.out.println(res); } } } // } Driver Code Ends class Solution { public static int minimumEdgeReversal(int[][] edges, int n, int m, int src, int dst) { //taking input ArrayList<ArrayList<pair>> graph = new ArrayList<>(); for(int i = 0 ;i < n ; i++) graph.add(new ArrayList<>()); for(int edge[] : edges){ //making into 0 based indexing graph.get(edge[0]-1).add(new pair(edge[1]-1,0)); graph.get(edge[1]-1).add(new pair(edge[0]-1,1)); } boolean visited[] = new boolean[n]; //making priority queue for djikstra PriorityQueue<pair> q = new PriorityQueue<>(); q.add(new pair(src-1,0)); //djikstra while(q.size()>0){ pair rem = q.poll(); int vtx = rem.vtx , wt = rem.wt; visited[vtx] = true; if(vtx == dst-1) return wt; for(pair nbr: graph.get(vtx)){ if(visited[nbr.vtx] == false){ q.add(new pair(nbr.vtx , nbr.wt + wt)); } } } return -1; } public static class pair implements Comparable<pair>{ int vtx , wt; pair(int vtx , int wt){ this.vtx = vtx; this.wt = wt; } public int compareTo(pair o){ return this.wt - o.wt; } } }
Comments