题目描述

给你一个字符串 initialCurrency，表示初始货币类型，并且你一开始拥有 1.0 单位的 initialCurrency。

另给你四个数组，分别表示货币对（字符串）和汇率（实数）：

• pairs1[i] = [startCurrency_i, targetCurrency_i] 表示在 第 1 天，可以按照汇率 rates1[i] 将 startCurrency_i 转换为 targetCurrency_i。
• pairs2[i] = [startCurrency_i, targetCurrency_i] 表示在 第 2 天，可以按照汇率 rates2[i] 将 startCurrency_i 转换为 targetCurrency_i。

此外，每种 targetCurrency 都可以以汇率 1 / rate 转换回对应的 startCurrency。

你可以在 第 1 天 使用 rates1 进行任意次数的兑换（包括 0 次），然后在 第 2 天 使用 rates2 再进行任意次数的兑换（包括 0 次）。

返回在两天兑换后，最大可能拥有的 initialCurrency 的数量。

注意：汇率是有效的，并且第 1 天和第 2 天的汇率之间相互独立，不会产生矛盾。

样例

输入：

initialCurrency = "EUR"
pairs1 = [["EUR","USD"],["USD","JPY"]], rates1 = [2.0,3.0]
pairs2 = [["JPY","USD"],["USD","CHF"],["CHF","EUR"]], rates2 = [4.0,5.0,6.0]

输出： 720.00000

解释：

根据题目要求，需要最大化最终的 EUR 数量，从 1.0 EUR 开始：

第 1 天：
将 EUR 换成 USD，得到 2.0 USD。
将 USD 换成 JPY，得到 6.0 JPY。
第 2 天：
将 JPY 换成 USD，得到 24.0 USD。
将 USD 换成 CHF，得到 120.0 CHF。
最后将 CHF 换回 EUR，得到 720.0 EUR。

输入： 

initialCurrency = "NGN",
pairs1 = [["NGN","EUR"]], rates1 = [9.0],
pairs2 = [["NGN","EUR"]], rates2 = [6.0]

输出： 1.50000

解释：

在第 1 天将 NGN 换成 EUR，并在第 2 天用反向汇率将 EUR 换回 NGN，可以最大化最终的 NGN 数量。

输入：

initialCurrency = "USD"
pairs1 = [["USD","EUR"]], rates1 = [1.0]
pairs2 = [["EUR","JPY"]], rates2 = [10.0]

输出： 1.00000

解释：

在这个例子中，不需要在任何一天进行任何兑换。

限制

• 1 <= initialCurrency.length <= 3
• initialCurrency 仅由大写英文字母组成。
• 1 <= n == pairs1.length <= 10
• 1 <= m == pairs2.length <= 10
• pairs1[i] == [startCurrency_i, targetCurrency_i]
• pairs2[i] == [startCurrency_i, targetCurrency_i]
• 1 <= startCurrencyi.length, targetCurrencyi.length <= 3
• startCurrency_i 和 targetCurrency_i 仅由大写英文字母组成。
• rates1.length == n
• rates2.length == m
• 1.0 <= rates1[i], rates2[i] <= 10.0
• 输入保证两个转换图在各自的天数中没有矛盾或循环。

算法

(宽度优先遍历) $O(n + m)$

1. 由于两天的货币转换相互独立，且都没不存在循环，所以可以通过宽度优先遍历，分别计算出每一天，从 1.0 个初始货币转为其他货币所能得到的数量。
2. 枚举第一天结束后持有的货币以及数量，此时已经预处理出了第二天从 1.0 个初始货币转为其他货币的数量，两个数字做除法，就是经过中间货币转换后，最后能得到的初始货币数量。

时间复杂度

• 两次宽度优先遍历，故总时间复杂度为 $O(n + m)$。

空间复杂度

• 需要 $O(n + m)$ 的额外空间存储邻接表，队列和转换数量数组。

C++ 代码

class Solution {
private:
    void bfs(const string &s,
        const unordered_map<string, vector<pair<string, double>>> &m,
        unordered_map<string, double> &d    
    ) {
        d[s] = 1.0;
        queue<string> q;
        q.push(s);

        while (!q.empty()) {
            auto u = q.front();
            q.pop();

            const auto adj = m.find(u);
            if (adj == m.end())
                continue;

            for (const auto &t : adj->second) {
                if (d.find(t.first) != d.end())
                    continue;

                d[t.first] = d[u] * t.second;
                q.push(t.first);
            }
        }
    }

public:
    double maxAmount(string initialCurrency, 
        vector<vector<string>>& pairs1, vector<double>& rates1,
        vector<vector<string>>& pairs2, vector<double>& rates2
    ) {
        unordered_map<string, vector<pair<string, double>>> m1;
        unordered_map<string, vector<pair<string, double>>> m2;

        for (int i = 0; i < pairs1.size(); i++) {
            m1[pairs1[i][0]].emplace_back(pairs1[i][1], rates1[i]);
            m1[pairs1[i][1]].emplace_back(pairs1[i][0], 1.0 / rates1[i]);
        }

        for (int i = 0; i < pairs2.size(); i++) {
            m2[pairs2[i][0]].emplace_back(pairs2[i][1], rates2[i]);
            m2[pairs2[i][1]].emplace_back(pairs2[i][0], 1.0 / rates2[i]);
        }

        unordered_map<string, double> d1;
        bfs(initialCurrency, m1, d1);

        unordered_map<string, double> d2;
        bfs(initialCurrency, m2, d2);

        double ans = 1.0;
        for (const auto &[k, v] : d1) {
            if (d2.find(k) == d2.end())
                continue;

            ans = max(ans, v / d2[k]);
        }

        return ans;
    }
};