Q17 Minimum edges(0-1 BFS) | Practice | GeeksforGeeks ( using djikstra)

//{ 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;
        }
    }
}