Currency exchange Conversion

基础版本的题目在这：https://leetcode.com/discuss/int ... currency-conversion
input:  一些列货币和汇率：[['USD', 'GBP', 0.77], ...['USD', 'CNY', 7]], where ['USD', 'GBP', 0.77] means 1 USD is equal to 0.77 GBP
货币起点和终点
output: 起点到终点的conversion rate

感觉这题用个BFS找任意一条路径顺便把weight乘上去就好了
但是我看到有人被问给定起点("CNY'), 能不能找到一种兑换方法获得最高的收益 。我有两个问题 1） 起点和终点如果相同要怎么做?
2） 允不允许反向兑换比如[['USD', 'CNY', 7]， ['CNY', 'USD', 1/7]? 如果这样要怎么做？

刷题小白还望解惑~

如果起点和终点都给定，目标是换到尽量多的终点货币，那Bellman-Ford应该可以解决。特别的如果起点和终点重合，那么要么不换就是最好的，要么可以无限赚。
第二个问题，lc原题是假设双向的，看他例子就知道了。不过不假设双向也没多大区别，只是路径可能不存在。

algrev 发表于 2022-11-19 17:25
如果起点和终点都给定，目标是换到尽量多的终点货币，那Bellman-Ford应该可以解决。特别的如果起点和终点重 ...

能问下双向的应该用什么方法做吗？我第一反应是，变成一个找无向图中起点到终点的所有可能路径，好像是个NP问题？

Bruno123 发表于 2022-11-19 19:11
能问下双向的应该用什么方法做吗？我第一反应是，变成一个找无向图中起点到终点的所有可能路径，好像是个 ...

双向的也是bellman-ford呀，甚至买卖汇率不是互为倒数也没关系。