Find the shortest distance between any pair of two different good nodes | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100005 NEW_LINE const int MAXI = 99999999 ; void add_edge ( vector < pair < int , int > > gr [ ] , int x , int y , int weight ) { gr [ x ] . push_back ( { y , weight } ) ; gr [ y ] . push_back ( { x , weight } ) ; } int minDistance ( vector < pair < int , int > > gr [ ] , int n , int dist [ ] , int vis [ ] , int a [ ] , int k ) { priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > q ; int ans = MAXI ; for ( int i = 1 ; i <= n ; i ++ ) { if ( ! a [ i ] ) continue ; for ( int j = 1 ; j <= n ; j ++ ) { dist [ j ] = MAXI ; vis [ j ] = 0 ; } dist [ i ] = 0 ; while ( ! q . empty ( ) ) q . pop ( ) ; q . push ( { 0 , i } ) ; int good = 0 ; while ( ! q . empty ( ) ) { int v = q . top ( ) . second ; q . pop ( ) ; if ( vis [ v ] ) continue ; vis [ v ] = 1 ; good += a [ v ] ; if ( dist [ v ] > ans ) break ; if ( good == 2 and a [ v ] ) { ans = min ( ans , dist [ v ] ) ; break ; } for ( int j = 0 ; j < gr [ v ] . size ( ) ; j ++ ) { int to = gr [ v ] [ j ] . first ; int weight = gr [ v ] [ j ] . second ; if ( dist [ v ] + weight < dist [ to ] ) { dist [ to ] = dist [ v ] + weight ; q . push ( { dist [ to ] , to } ) ; } } } } return ans ; } int main ( ) { int n = 5 , m = 5 ; vector < pair < int , int > > gr [ N ] ; 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 [ N ] , vis [ N ] , dist [ N ] ; a [ 1 ] = a [ 3 ] = a [ 5 ] = 1 ; cout << minDistance ( gr , n , dist , vis , a , k ) ; return 0 ; }