Path with smallest product of edges with weight >= 1 | C ++ implementation of the approach ; Function to return the smallest product of edges ; If the source is equal to the destination ; Initialise the priority queue ; Visited array ; While the priority - queue is not empty ; Current node ; Current product of distance ; Popping the top - most element ; If already visited continue ; Marking the node as visited ; If it is a destination node ; Traversing the current node ; If no path exists ; Driver code ; Graph as adjacency matrix ; Input edges ; Source and destination ; Dijkstra
#include <bits/stdc++.h> NEW_LINE using namespace std ; double dijkstra ( int s , int d , vector < vector < pair < int , double > > > gr ) { if ( s == d ) return 0 ; set < pair < int , int > > pq ; pq . insert ( { 1 , s } ) ; bool v [ gr . size ( ) ] = { 0 } ; while ( pq . size ( ) ) { int curr = pq . begin ( ) -> second ; int dist = pq . begin ( ) -> first ; pq . erase ( pq . begin ( ) ) ; if ( v [ curr ] ) continue ; v [ curr ] = 1 ; if ( curr == d ) return dist ; for ( auto it : gr [ curr ] ) pq . insert ( { dist * it . second , it . first } ) ; } return -1 ; } int main ( ) { int n = 3 ; vector < vector < pair < int , double > > > gr ( n + 1 ) ; gr [ 1 ] . push_back ( { 3 , 9 } ) ; gr [ 2 ] . push_back ( { 3 , 1 } ) ; gr [ 1 ] . push_back ( { 2 , 5 } ) ; int s = 1 , d = 3 ; cout << dijkstra ( s , d , gr ) ; return 0 ; }