3387: Maximize Amount After Two Days of Conversions

import java.util.*;

class Solution {
    public double maxAmount(String initialCurrency, String[][] pairs1, double[] rates1, String[][] pairs2, double[] rates2) {
        Map<String, Map<String, Double>> graph1 = buildGraph(pairs1, rates1);
        Map<String, Map<String, Double>> graph2 = buildGraph(pairs2, rates2);
        
        Map<String, Map<String, Double>> day1Rates = floydWarshall(graph1);
        Map<String, Map<String, Double>> day2Rates = floydWarshall(graph2);
        
        Map<String, Double> day1Amounts = new HashMap<>();
        for (String currency : day1Rates.keySet()) {
            if (day1Rates.get(initialCurrency).containsKey(currency)) {
                day1Amounts.put(currency, day1Rates.get(initialCurrency).get(currency));
            }
        }
        day1Amounts.put(initialCurrency, 1.0);
        
        double maxAmount = 1.0;
        for (Map.Entry<String, Double> entry : day1Amounts.entrySet()) {
            String currency = entry.getKey();
            double amount = entry.getValue();
            if (day2Rates.containsKey(currency)) {
                maxAmount = Math.max(maxAmount, amount * day2Rates.get(currency).get(initialCurrency));
            }
        }
        
        return maxAmount;
    }
    
    private Map<String, Map<String, Double>> buildGraph(String[][] pairs, double[] rates) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < pairs.length; i++) {
            String from = pairs[i][0];
            String to = pairs[i][1];
            double rate = rates[i];
            
            graph.putIfAbsent(from, new HashMap<>());
            graph.putIfAbsent(to, new HashMap<>());
            
            graph.get(from).put(to, rate);
            graph.get(to).put(from, 1.0 / rate);
        }
        return graph;
    }
    
    private Map<String, Map<String, Double>> floydWarshall(Map<String, Map<String, Double>> graph) {
        List<String> currencies = new ArrayList<>(graph.keySet());
        Map<String, Map<String, Double>> dist = new HashMap<>();
        
        // Initialize distances
        for (String from : currencies) {
            dist.put(from, new HashMap<>());
            for (String to : currencies) {
                if (from.equals(to)) {
                    dist.get(from).put(to, 1.0);
                } else if (graph.get(from).containsKey(to)) {
                    dist.get(from).put(to, graph.get(from).get(to));
                } else {
                    dist.get(from).put(to, 0.0);
                }
            }
        }
        
        // Floyd-Warshall algorithm
        for (String k : currencies) {
            for (String i : currencies) {
                for (String j : currencies) {
                    double newDist = dist.get(i).get(k) * dist.get(k).get(j);
                    if (newDist > dist.get(i).get(j)) {
                        dist.get(i).put(j, newDist);
                    }
                }
            }
        }
        
        return dist;
    }
}

from collections import defaultdict

class Solution:
    def maxAmount(self, initialCurrency: str, pairs1: List[List[str]], rates1: List[float], 
                 pairs2: List[List[str]], rates2: List[float]) -> float:
        
        def build_graph(pairs, rates):
            graph = defaultdict(dict)
            for (from_curr, to_curr), rate in zip(pairs, rates):
                graph[from_curr][to_curr] = rate
                graph[to_curr][from_curr] = 1.0 / rate
            return graph
        
        def floyd_warshall(graph):
            currencies = list(graph.keys())
            dist = defaultdict(dict)
            
            # Initialize distances
            for from_curr in currencies:
                for to_curr in currencies:
                    if from_curr == to_curr:
                        dist[from_curr][to_curr] = 1.0
                    elif to_curr in graph[from_curr]:
                        dist[from_curr][to_curr] = graph[from_curr][to_curr]
                    else:
                        dist[from_curr][to_curr] = 0.0
            
            # Floyd-Warshall algorithm
            for k in currencies:
                for i in currencies:
                    for j in currencies:
                        dist[i][j] = max(dist[i][j], dist[i][k] * dist[k][j])
            
            return dist
        
        graph1 = build_graph(pairs1, rates1)
        graph2 = build_graph(pairs2, rates2)
        
        day1_rates = floyd_warshall(graph1)
        day2_rates = floyd_warshall(graph2)
        
        day1_amounts = {}
        for currency in day1_rates[initialCurrency]:
            day1_amounts[currency] = day1_rates[initialCurrency][currency]
        day1_amounts[initialCurrency] = 1.0
        
        max_amount = 1.0
        for currency, amount in day1_amounts.items():
            if currency in day2_rates:
                max_amount = max(max_amount, amount * day2_rates[currency][initialCurrency])
        
        return max_amount