[算法] 求助一道算法题,求最便宜路径


问题如下

你正在玩一款游戏。一共有 n 个镇,现在你在 a 镇并想走到 b 镇。与其他游戏中可以不停地走上几个小时不同,在这个游戏里你不能这样做。你有当前的耐力点数,如果耐力降至 0,则将无法再走下去。

在相距 d 公里的两个城镇之间的道路上行走会消耗 d 耐力点。如果你目前没有至少 d 耐力点,那么你将不能走这条路。

每个城镇都有一个旅馆可以休息。每休息一小时,就会恢复 1 点耐力,直至你的最大耐力点 m 。每家旅馆都有不同的每个小时休息价格。

你不想在旅馆里浪费不必要的钱。请问从起始城镇 a 到目的地城镇 b 最便宜的价格是多少?

本来以为是最短路径问题,但想了一下如果当前体力不够完全可以绕路去附近比较近的城市休息才可以保证总价格最便宜。甚至有可能附近的城市是死路,但可以过去恢复完耐力再往回走,所以也不能简单地把每个城市的旅馆价格作为权重。

想了很久也没想出解法,所以发出来问问大家意见。

发表回复

您的电子邮箱地址不会被公开。