poj1860_最短路bellman Ford算法应用 题意简述某城市有M（1算法分析本题可抽象为一张有N个节点的有向图，一个兑换站就是它所兑换的两种货币间的两条有向边。边的权值有两个：汇率及手续费。问题可化简为：从定点出发找正权环。由于可以通过无限次走正权环使得收益趋于无穷，所以不考虑返程开销。容易发现，这是Bellman-Ford算法的逆用。将求最短路改为求最长路，再找可以无限松弛的正环，即可得解。只 ACM--题目 2024-09-04 32 点赞 0 评论 48 浏览
