Shortest path with exactly k edges in a directed and weighted graph | Set 2 | C ++ implementation of the above approach ; Function to find the smallest path with exactly K edges ; Array to store dp ; Initialising the array ; Loop to solve DP ; Initialising next state ; Recurrence relation ; Returning final answer ; Driver code ; Input edges ; Source and Destination ; Number of edges in path ; Calling the function
#include <bits/stdc++.h> NEW_LINE #define inf  100000000 NEW_LINE using namespace std ; double smPath ( int s , int d , vector < pair < pair < int , int > , int > > ed , int n , int k ) { int dis [ n + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) dis [ i ] = inf ; dis [ s ] = 0 ; for ( int i = 0 ; i < k ; i ++ ) { int dis1 [ n + 1 ] ; for ( int j = 0 ; j <= n ; j ++ ) dis1 [ j ] = inf ; for ( auto it : ed ) dis1 [ it . first . second ] = min ( dis1 [ it . first . second ] , dis [ it . first . first ] + it . second ) ; for ( int i = 0 ; i <= n ; i ++ ) dis [ i ] = dis1 [ i ] ; } if ( dis [ d ] == inf ) return -1 ; else return dis [ d ] ; } int main ( ) { int n = 4 ; vector < pair < pair < int , int > , int > > ed ; ed = { { { 0 , 1 } , 10 } , { { 0 , 2 } , 3 } , { { 0 , 3 } , 2 } , { { 1 , 3 } , 7 } , { { 2 , 3 } , 7 } } ; int s = 0 , d = 3 ; int k = 2 ; cout << smPath ( s , d , ed , n , k ) ; }