human
Minimum cost path from source node to destination node via K intermediate nodes | Function to find the minimum cost path from the source vertex to destination vertex via K intermediate vertices.
Initialize the adjacency list.
Generate the adjacency list.
Initialize the minimum priority queue.
Stores the minimum cost to travel between vertices via K intermediate nodes.
Push the starting vertex , cost to reach and the number of remaining vertices.
Pop the top element of the stack.
If destination is reached.
Return the cost.
If all stops are exhausted.
Find the neighbour with minimum cost.
Pruning.
Update cost.
Update priority queue.
If no path exists.
Driver Code.
Function Call to find the path from src to dist via k nodes having least sum of weights"
Solution in Python:
 ... Can you provide a code to minimum cost path from source node to destination node via K intermediate nodes and the other steps required?
assistant
#Here is code to minimum cost path from source node to destination node via K intermediate nodes and the other steps required.
 def leastWeightedSumPath ( n , edges , src , dst , K ) :
	graph = [ [ ] for i in range ( 3 ) ]
	for edge in edges :
		graph [ edge [ 0 ] ] . append ( [ edge [ 1 ] , edge [ 2 ] ] )
	pq = [ ]
	costs = [ [ 10 ** 9 for i in range ( K + 2 ) ] for i in range ( n ) ]
	costs [ src ] [ K + 1 ] = 0
	pq . append ( [ 0 , src , K + 1 ] )
	pq = sorted ( pq ) [ : : - 1 ]
	while ( len ( pq ) > 0 ) :
		top = pq [ - 1 ]
		del pq [ - 1 ]
		if ( top [ 1 ] == dst ) :
			return top [ 0 ]
		if ( top [ 2 ] == 0 ) :
			continue
		for neighbor in graph [ top [ 1 ] ] :
			if ( costs [ neighbor [ 0 ] ] [ top [ 2 ] - 1 ] < neighbor [ 1 ] + top [ 0 ] ) :
				continue
			costs [ neighbor [ 0 ] ] [ top [ 2 ] - 1 ] = neighbor [ 1 ] + top [ 0 ]
			pq . append ( [ neighbor [ 1 ] + top [ 0 ] , neighbor [ 0 ] , top [ 2 ] - 1 ] )
		pq = sorted ( pq ) [ : : - 1 ]
	return - 1
if __name__ == ' _ _ main _ _ ' :
	n , src , dst , k = 3 , 0 , 2 , 1
	edges = [ [ 0 , 1 , 100 ] , [ 1 , 2 , 100 ] , [ 0 , 2 , 500 ] ]
	print ( leastWeightedSumPath ( n , edges , src , dst , k ) )