这是我在面试中遇到的一个问题:
给你一张一个国家城市间的飞机地图，基本上是一个有向图，用权重表示城市间飞机的成本。你还获得了一张优惠券，可以在任何一次航班上获得50%的折扣。找出你在两个城市之间旅行的最低费用?
这个问题的基本算法是Dijkstra的最短路径算法。但是，我们需要找到一个包含优惠券的方法。
我们可以通过引入券息状态来实现这一点。不是available就是spent。在每个机场，状态可以是两者之一。所以我们可以复制顶点的数量(对于机场)。对于每个机场，一个顶点将具有available状态，一个顶点将具有spent状态。边缘需要稍微改变一下。从spent状态的顶点到available状态的顶点是不可能的。在另一个方向上，原始成本减半。
现在我们想要找到从起始机场(available状态的顶点)到目的地机场(spent状态的顶点)的最小成本路径。这可以通过Dijkstra的plain算法实现。