Find the shortest distance between any pair of two different good nodes | Java program to find the shortest pairwise distance between any two different good nodes . ; Function to add edges ; Function to find the shortest distance between any pair of two different good nodes ; Keeps minimum element on top ; To keep required answer ; If it is not good vertex ; Keep all vertices not visited and distance as MAXI ; Distance from ith vertex to ith is zero ; Make queue empty ; Push the ith vertex ; Count the good vertices ; Take the top element ; Remove it ; If it is already visited ; Count good vertices ; If distance from vth vertex is greater than ans ; If two good vertices are found ; Go to all adjacent vertices ; If distance is less ; Return the required answer ; Driver code ; Number of vertices and edges ; Function call to add edges ; Number of good nodes ; To keep good vertices
import java . util . ArrayList ; import java . util . Comparator ; import java . util . PriorityQueue ; class GFG { static class Pair { int first , second ; public Pair ( int first , int second ) { this . first = first ; this . second = second ; } public Pair ( ) { } } static final int N = 100005 ; static final int MAXI = 99999999 ; static void add_edge ( ArrayList < Pair > gr [ ] , int x , int y , int weight ) { gr [ x ] . add ( new Pair ( y , weight ) ) ; gr [ y ] . add ( new Pair ( x , weight ) ) ; } static int minDistance ( ArrayList < Pair > gr [ ] , int n , int dist [ ] , int vis [ ] , int a [ ] , int k ) { PriorityQueue < Pair > q = new PriorityQueue < > ( new Comparator < Pair > ( ) { public int compare ( Pair p1 , Pair p2 ) { if ( p1 . first == p2 . first ) { return p1 . second - p2 . second ; } return p1 . first - p2 . first ; } } ) ; int ans = MAXI ; for ( int i = 1 ; i <= n ; i ++ ) { if ( a [ i ] == 0 ) continue ; for ( int j = 1 ; j <= n ; j ++ ) { dist [ j ] = MAXI ; vis [ j ] = 0 ; } dist [ i ] = 0 ; while ( ! q . isEmpty ( ) ) q . poll ( ) ; q . add ( new Pair ( 0 , i ) ) ; int good = 0 ; while ( ! q . isEmpty ( ) ) { int v = q . peek ( ) . second ; q . poll ( ) ; if ( vis [ v ] != 0 ) continue ; vis [ v ] = 1 ; good += a [ v ] ; if ( dist [ v ] > ans ) break ; if ( good == 2 && a [ v ] != 0 ) { ans = Math . min ( ans , dist [ v ] ) ; break ; } for ( int j = 0 ; j < gr [ v ] . size ( ) ; j ++ ) { int to = gr [ v ] . get ( j ) . first ; int weight = gr [ v ] . get ( j ) . second ; if ( dist [ v ] + weight < dist [ to ] ) { dist [ to ] = dist [ v ] + weight ; q . add ( new Pair ( dist [ to ] , to ) ) ; } } } } return ans ; } public static void main ( String [ ] args ) { int n = 5 , m = 5 ; @ SuppressWarnings ( " unchecked " ) ArrayList < Pair > [ ] gr = new ArrayList [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { gr [ i ] = new ArrayList < Pair > ( ) ; } add_edge ( gr , 1 , 2 , 3 ) ; add_edge ( gr , 1 , 2 , 3 ) ; add_edge ( gr , 2 , 3 , 4 ) ; add_edge ( gr , 3 , 4 , 1 ) ; add_edge ( gr , 4 , 5 , 8 ) ; int k = 3 ; int [ ] a = new int [ N ] , vis = new int [ N ] , dist = new int [ N ] ; a [ 1 ] = a [ 3 ] = a [ 5 ] = 1 ; System . out . println ( minDistance ( gr , n , dist , vis , a , k ) ) ; } }