PROBLEM LINK:Author: vishfrnds DIFFICULTY:MEDIUM PREREQUISITES:dijkstra's algorithm PROBLEM:Given a graph of N nodes. ith node has a height H[i], and cost C[i]. You can travel nodes in one of the mode either nondecreasing order of height or nonincreasing order of height of nodes. Whenever you change mode on ith node it will cost you C[i]. Find the path of minimum cost from node 1 to N. QUICK EXPLANATION:Split the given graph into two graphs each of N nodes. Where each graph have a subset directed edges of 0 cost, representing single mode only. Connect the corresponding nodes from both graph with undirected edge of cost C[i]. Add a source node and connect it with node 1 of both graphs with cost C[i]. Add a destination node and connect it with node N of both graphs with cost 0. Apply Dijkstra algorithm to find smallest cost path between source and destination. EXPLANATION:Make a copy of given graph G1, let it be G2. G1 will have a directed edge from node A to B if and only if H[A] <= H[B] and there was edge between A and B in orignal graph, delete all other edges. G2 will have a directed edge from node A to B if and only if H[A] >= H[B] and there was edge between A and B in orignal graph, delete all other edges. Now G1 represents mode "up the road" (i.e. nondecreasing mode). Now G2 represents mode "down the road" (i.e. nonincreasing mode). All the edges in G1 and G2 have cost 0. This represent it will not cost you anything as long as you are in single graph. Now to allow changing of mode we will connect corresponding nodes of both the graph with cost C[i] of that node. Thus, whenever you will change mode on ith node it will cost C[i]. Now we will add a source and destination node. Source node will be connected to node 1 of G1 with cost C[1] and node 1 of G2 with cost C[1]. Because you need to pay to chose initial mode. Destination node will be connected to node N of G1 with cost 0 and node N of G2 with cost 0. Because it makes no difference wether you end up on G1's node N or G2's node N. So if given graph had n nodes e edges, final graph will have node N = 2 * n + 2 and edges E = e + n + 4 Now we will use dijkstra's algorithm to find minimum cost path from source to destination in this new graph. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution.
This question is marked "community wiki".
asked 07 Sep '15, 01:58
