# Parse an input with some currencies conversions and use Dijkstra to find a path to convert from functools import reduce """ Input should look like this : FROM_CUR;AMOUNT;TO_CUR Number of conversions FROM_CUR;TO_CUR;UNIT_CONVERSION FROM_CUR;TO_CUR;UNIT_CONVERSION FROM_CUR;TO_CUR;UNIT_CONVERSION eg: EUR;912.12;USD 4 EUR;CAD;1.12 CAD;JPY;119 CAD;AUD;0.98 AUD;USD;1.28 Dijkstra algorithm will be applied to the conversion graph (number of conversion required). Using the prev dictionary we retrace the path to reach our currency and reduce the conversion rates. """ # First line : Get the fields from_, value, to_ = input().split(";") # For the number of line, read each rate raw_table = [input() for _ in range(int(input()))] # Create a conversion table with their inverse (1/rate) conversion = [{"from": x[0], "to": x[1], "val": float(x[2])} for x in [_.split(";") for _ in raw_table]] conversion.extend([{"from": c["to"], "to": c["from"], "val": round(1/c["val"], 4)} for c in conversion]) # Dijkstra distance and prev dicts dist = dict() prev = dict() # Usable vertices set v_set = set() # Fill the set and dictionaries with our conversion table for v in {c["from"] for c in conversion}: dist[v] = float("inf") prev[v] = None v_set = v_set | {v} # Starting point is 0 far away from itself dist[from_] = 0 # Dijkstra algorithm (Read the distances from the closest available vertex) while len(v_set) > 0: u = min(v_set, key=lambda v: dist[v]) # Select closest v_set.remove(u) # Remove from the available vertex set for neigh in [n["to"] for n in conversion if n["from"] == u]: # Get the current vertex neighbours alt = dist[u] + 1 # Using a distance of 1 because it represent a conversion step if alt < dist[neigh]: dist[neigh] = alt prev[neigh] = u # The compute array will contain each needed rate (Just need the product to have the final rate) compute = [] z = to_ while prev[z] is not None: # Iterate over the prevs to trace the route before = prev[z] compute.append([do["val"] for do in conversion if do["from"] == before and do["to"] == z][0]) z = before print(int(value) * reduce(lambda acc, v: acc*v, compute, 1))