森森旅游pta

魔都地铁的计价规则是：起步价2元，出发站与到达站的最短距离每K公里增加1元车费,以上就是关于森森旅游的PTA问题的详细解答，希望对您有所帮助,森森旅游pta

关于森森旅游的PTA问题，以下是详细解答：

1. 森森旅游的背景

森森决定去Z省旅游一下。Z省有n座城市(从1到n编号)以及m条连接两座城市的有向旅行线路(例如自驾、长途汽车、火车、飞机、轮船等)，每次经过一条旅行线路时都需要支付该线路的费用。

2. 旅游金计划

Z省为了鼓励大家在省内多逛逛，推出了旅游金计划:在i号城市可以用1元现金兑换ai元旅游金(只要现金足够，可以无限次兑换)。城市间的交通即可以使用现金支付路费，也可以用旅游金支付。

3. 如何规划旅程

具体的旅程规划需要用到算法，比如Dijkstra算法。这种算法可以帮助我们找到从1号点到所有任意其他点的最少现金和从任意点到n号点所需要的最少旅游金。

4. 注意事项

在规划旅程时，我们需要注意到每次兑换旅行币都要将现金兑完，所以可以将旅程拆解成两段不同的最短路，一段是从1点出发到i点代表用现金的最短路，直接Dijkstra即可；另一段则是从i点到达n点的代表用旅行货币的最短路，反向建图再Dijkstra即可。

5. 实际案例

在一个实际的案例中，森森来到了传说中的地铁之城——魔都，打算好好过一把坐地铁的瘾！魔都地铁的计价规则是：起步价2元，出发站与到达站的最短距离（即计费距离）每K公里增加1元车费。

以上就是关于森森旅游的PTA问题的详细解答，希望对您有所帮助。