森森旅游 天梯赛：森森旅游天梯赛怎么算

森森旅游 天梯赛是一个关于旅行路线规划的问题,在这个问题中，森森决定去Z省旅游，Z省有n座城市（从1到n编号）以及m条连接两座城市的有向旅行线路,每次经过一条旅行线路时都需要支付该线路的费用，但这个收费标准可能不止一种，例如车票跟机票一般不是一个价格,Z省为了鼓励大家在省内多逛逛，推出了旅游金计划：在i号城市可以用1元现金兑换ai元旅游金（只要现金足够，可以无限次兑换）,城市间的交通即可以使用现金支付路费，也可以用旅游金支付,具体来说，当通过第j条旅行线路时，可以用cj元现金或dj元旅游金支付路费,对于不同的线路，旅客可以自由选择不同的支付方式

森森旅游 天梯赛

问题描述

森森旅游 天梯赛是一个关于旅行路线规划的问题。在这个问题中，森森决定去Z省旅游，Z省有n座城市（从1到n编号）以及m条连接两座城市的有向旅行线路。每次经过一条旅行线路时都需要支付该线路的费用，但这个收费标准可能不止一种，例如车票跟机票一般不是一个价格。Z省为了鼓励大家在省内多逛逛，推出了旅游金计划：在i号城市可以用1元现金兑换ai元旅游金（只要现金足够，可以无限次兑换）。城市间的交通即可以使用现金支付路费，也可以用旅游金支付。具体来说，当通过第j条旅行线路时，可以用cj元现金或dj元旅游金支付路费。对于不同的线路，旅客可以自由选择不同的支付方式。

森森决定从1号城市出发，到n号城市去。他打算在出发前准备一些现金，并在途中的某个城市将剩余现金全部换成旅游金后继续旅游，直到到达n号城市为止。Z省政府会根据每个城市参与活动的情况调整汇率（即调整在某个城市1元现金能换多少旅游金）。现在需要帮助森森计算一下，在每次调整之后最少需要携带多少现金才能完成他的旅程。

解决方法

解决这个问题的一种方法是使用Dijkstra算法。首先，我们需要建立一个图，其中每个节点代表一个城市，每条边代表一条旅行线路，边的权重是该线路的费用。然后，我们可以从1号城市开始，使用Dijkstra算法计算到达每个城市的最小费用。在计算过程中，我们需要考虑到两种支付方式：现金和旅游金，并选择费用最低的支付方式。同时，我们还需要记录下在每个城市进行旅游金兑换的最小现金量。

由于可能存在多个兑换点，所以我们需要考虑多种路径和费用。具体来说，我们可以使用堆优化版本的Dijkstra模板来解决这个问题。在这个模板中，我们需要将dist数组初始化为long long类型，以存储较大的数值。我们还需要使用multiset来维护每个城市的最小费用。

在每次汇率调整之后，我们需要重新计算从1号城市到达每个城市的最小费用，并输出调整后的森森至少需要准备多少现金，才能按他的计划从1号城市旅行到n号城市。

注意事项

在解决问题时，我们需要注意以下几点：

• 每次只能选择一种支付方式，不可同时使用现金和旅游金混合支付。
• 如果森森决定在途中的某个城市兑换旅游金，那么他必须将剩余现金全部、一次性兑换，剩下的旅途将完全使用旅游金支付。
• Z省政府会根据每个城市参与活动的情况调整汇率，因此在旅程中，森森需要灵活应对这些调整。