题目重点：将报价表示成有向乘法图，区分能否到达和最佳兑换率，先厘清多跳与套利循环的规则。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 汇率 r>0，A:B:r 表示 1 A 可换 r B；反向可按 1/r 构边，手续费、买卖差价、时间版本均未在题目公开。
- 同货币按汇率 1 返回；若同一货币对有多条报价，训练版保留全部可用边并取最优，正式题要确认是否仅一条。
- 限一次中转指最多两条边；‘最佳’训练版限制为简单路径（货币不重复），这样结果有限。若允许重复且某环乘积>1，则最佳率可以无界。
解题路线
- 解析报价并同时建立正向 r 与反向 1/r 边；直接查边需明确多报价择优及浮点误差。
- 最多一中转时枚举 from 邻居 x，若 x→to 存在，比较 r(from,x)×r(x,to)，也包含直接路径。
- 任意多跳只求可达可 BFS/DFS，记录 visited 避免环；但 BFS 首次找到的路径保证的是边数最少，绝非乘积最高。
- 最佳简单路径可对较小货币图 DFS 回溯并维护已访问集合，最坏指数级。若允许最多 K 跳，用 max-product DP：best[k][v]=max_u(best[k−1][u]×rate(u,v))；这允许重复货币，需检测正乘积环。可对收益取 log 后用 Bellman-Ford 风格检查正环，但货币报价图可能有真实买卖差价，不能自动假设互逆边都可按同价无限套利。
- 返回路径同时记录前驱及计算用的报价快照；输出金额时再按货币精度舍入，不能逐边随意 round 造成不一致。
手动走一遍
训练例 AUD→USD=0.7、USD→CAD=1.2，则 AUD→CAD 的两跳率为 0.84；CAD→USD 的反向率为 1/1.2。若另一条 AUD→JPY→CAD 率 0.9，最佳一中转应选后者。若存在 A→B=2、B→A=0.6，则每绕一圈乘 1.2，允许无限重复时‘最佳’无有限答案。
规模与取舍
V 种货币、E 条报价：建图 O(E)，可达 BFS O(V+E)，一中转扫描邻居 O(E) 上界；枚举简单路径最坏 O(V!)，最多 K 跳 DP O(KE)。用 log 变换时要考虑浮点误差与容差。
易错点与追问
容易失分的边界
- 只建单向边，漏掉题帖明确提到的反向查询。
- 把 BFS 的首次到达路径当作最高兑换率。
- 不定义环路却声称任意多跳最大汇率总可求。
- 把市场汇率的反向数学关系直接当成真实双向可成交报价，忽略手续费与点差。
继续深挖
- 若报价时间戳不同，跨时点组成的路径是否有效？
- 允许最多 K 次交易且可能重复货币时，如何检测收益环并返回证据？
- 在真实支付中如何处理汇率锁定、舍入与报价过期？
