Problem statement

https://binarysearch.com/problems/Best-Currency-Path/

Solution

Here we can use Bellman-Ford algorithm.

Complexity

It is O(mn) for time and O(n) for space. We need to adapt it a bit for multiplication instead of sum: it is equivalent to use logarithms of values.

Code

class Solution:
    def solve(self, source, target, S, T, R):
        dist = defaultdict(lambda: -float("inf"))
        dist[source] = 1
        n = len(set(S) | set(T))

        for _ in range(n):
            for u, v, d in zip(S, T, R):
                if dist[u]*d > dist[v]:
                    dist[v] = dist[u]*d

        for u, v, d in zip(S, T, R):
            if dist[u]*d > dist[v]:
                return -1

        return dist[target] if dist[target] != -float("inf") else 0