Reference no: EM13371039

Algorithm Analysis with Advanced Data Structures

Alchemy

-Mines of Oreland yield unlimited amounts of silver, but no gold. Unfortunately, rich noblemen from the neighboring kingdom of Eldorado are interested only in buying gold.

-The resourceful merchants of Oreland want to hire alchemists to change the silver into gold. However, the skills of alchemists are somewhat limited - they cannot transmute any metal into any other, so the process of changing silver into gold may have to go through a sequence of transmutations involving other metals.

-For each transmutation, alchemists charge a fee, which depends on the pairs of metals involved in the transmutation.

-Your task is to write a program to help the merchants devise a sequence of transmutations that would change silver into gold with the smallest possible total fee paid to the alchemists.

Details

-Your program should read input from System.in:

-in the first line of input: a number of transmutations alchemists know how to handle

-for each transmutation the alchemists know: the metals it involves and its cost, as a triple, each in a separate line of input:

MetalX MetalY CostXY where:

-MetalX is the atomic number of the input (substrate) metal
-MetalY is the atomic number of the output (product) metal
-CostXY is the fee alchemists charge for transmuting 1 pound of MetalX into 1 pound of MetalY
-Your task is to find the sequence of transmutations, starting with silver (Ag, atomic number 47) and ending with gold (Au, atomic number 79), that has the smallest sum of fees for transmuting 1 pound of Ag into 1 pound of Au
-Your program should just return on System.out one number: the smallest possible sum of fees (it should not return the actual sequence)
-There will always be at least one way to change silver into gold

-Correct output: 9

Example
-Input:
10
47 28 5
28 29 3
26 79 6
28 26 2
79 26 4
28 79 9
26 47 7
29 28 2
47 29 10
29 79 1

-The sequence behind this correct output is (but your program shouldn't print it): 47,28,29,79 (that is: silver, nickel, copper, gold)