Maximize shortest path between given vertices by adding a single edge | Function that performs BFS Traversal ; Fill initially each distance as INF fill ( dist , dist + N , 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 ] ; Prminimum cost ; Driver Code ; Given nodes and edges ; Sort the selected nodes ; Given edges ; Function Call
def bfs ( x , s ) : NEW_LINE INDENT global edges , dist NEW_LINE q = [ 0 for i in range ( 200000 ) ] NEW_LINE qh , qt = 0 , 0 NEW_LINE q [ qh ] = s NEW_LINE qh += 1 NEW_LINE dist [ x ] [ s ] = 0 NEW_LINE while ( qt < qh ) : NEW_LINE INDENT xx = q [ qt ] NEW_LINE qt += 1 NEW_LINE for y in edges [ xx ] : NEW_LINE INDENT if ( dist [ x ] [ y ] == 10 ** 18 ) : NEW_LINE INDENT dist [ x ] [ y ] = dist [ x ] [ xx ] + 1 NEW_LINE q [ qh ] = y NEW_LINE qh += 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT def shortestPathCost ( selected , K ) : NEW_LINE INDENT global dist , edges NEW_LINE data = [ ] NEW_LINE bfs ( 0 , 0 ) NEW_LINE bfs ( 1 , N - 1 ) NEW_LINE for i in range ( K ) : NEW_LINE INDENT data . append ( [ dist [ 0 ] [ selected [ i ] ] - dist [ 1 ] [ selected [ i ] ] , selected [ i ] ] ) NEW_LINE DEDENT data = sorted ( data ) NEW_LINE best = 0 NEW_LINE MAX = - 10 ** 18 NEW_LINE for it in data : NEW_LINE INDENT a = it [ 1 ] NEW_LINE best = max ( best , MAX + dist [ 1 ] [ a ] ) NEW_LINE MAX = max ( MAX , dist [ 0 ] [ a ] ) NEW_LINE DEDENT print ( min ( dist [ 0 ] [ N - 1 ] , best + 1 ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT edges = [ [ ] for i in range ( 5 ) ] NEW_LINE dist = [ [ 10 ** 18 for i in range ( 1000005 ) ] for i in range ( 2 ) ] NEW_LINE N , M = 5 , 4 NEW_LINE K = 2 NEW_LINE selected = [ 1 , 3 ] NEW_LINE selected = sorted ( selected ) NEW_LINE edges [ 0 ] . append ( 1 ) NEW_LINE edges [ 1 ] . append ( 0 ) NEW_LINE edges [ 1 ] . append ( 2 ) NEW_LINE edges [ 2 ] . append ( 1 ) NEW_LINE edges [ 2 ] . append ( 3 ) NEW_LINE edges [ 3 ] . append ( 2 ) NEW_LINE edges [ 3 ] . append ( 4 ) NEW_LINE edges [ 4 ] . append ( 3 ) NEW_LINE shortestPathCost ( selected , K ) NEW_LINE DEDENT