Maximize shortest path between given vertices by adding a single edge | C ++ program for the above approach ; To store graph as adjacency list ; To store the shortest path ; Function that performs BFS Traversal ; Fill initially each distance as INF ; Perform BFS ; Traverse the current edges ; Update the distance ; Insert in queue ; Function that maximizes the shortest path between source and destination vertex by adding a single edge between given selected nodes ; To update the shortest distance between node 1 to other vertices ; To update the shortest distance between node N to other vertices ; Store the values x [ i ] - y [ i ] ; Sort all the vectors of pairs ; Traverse data [ ] ; Maximize x [ a ] - y [ b ] ; Print minimum cost ; Driver Code ; Given nodes and edges ; Sort the selected nodes ; Given edges ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int INF = 1e9 + 7 ; int N , M ; vector < int > edges [ 200005 ] ; int dist [ 2 ] [ 200000 ] ; void bfs ( int * dist , int s ) { int q [ 200000 ] ; fill ( dist , dist + N , INF ) ; int qh = 0 , qt = 0 ; q [ qh ++ ] = s ; dist [ s ] = 0 ; while ( qt < qh ) { int x = q [ qt ++ ] ; for ( int y : edges [ x ] ) { if ( dist [ y ] == INF ) { dist [ y ] = dist [ x ] + 1 ; q [ qh ++ ] = y ; } } } } void shortestPathCost ( int selected [ ] , int K ) { vector < pair < int , int > > data ; bfs ( dist [ 0 ] , 0 ) ; bfs ( dist [ 1 ] , N - 1 ) ; for ( int i = 0 ; i < K ; i ++ ) { data . emplace_back ( dist [ 0 ] [ selected [ i ] ] - dist [ 1 ] [ selected [ i ] ] , selected [ i ] ) ; } sort ( data . begin ( ) , data . end ( ) ) ; int best = 0 ; int MAX = - INF ; for ( auto it : data ) { int a = it . second ; best = max ( best , MAX + dist [ 1 ] [ a ] ) ; MAX = max ( MAX , dist [ 0 ] [ a ] ) ; } printf ( " % d STRNEWLINE " , min ( dist [ 0 ] [ N - 1 ] , best + 1 ) ) ; } int main ( ) { N = 5 , M = 4 ; int K = 2 ; int selected [ ] = { 1 , 3 } ; sort ( selected , selected + K ) ; edges [ 0 ] . push_back ( 1 ) ; edges [ 1 ] . push_back ( 0 ) ; edges [ 1 ] . push_back ( 2 ) ; edges [ 2 ] . push_back ( 1 ) ; edges [ 2 ] . push_back ( 3 ) ; edges [ 3 ] . push_back ( 2 ) ; edges [ 3 ] . push_back ( 4 ) ; edges [ 4 ] . push_back ( 3 ) ; shortestPathCost ( selected , K ) ; return 0 ; }