首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >两个顶点之间的最短路径何时才能减少50%的边权?

问两个顶点之间的最短路径何时才能减少50%的边权?
EN

Stack Overflow用户
提问于 2014-08-10 16:01:53
回答 1查看 844关注 0票数 3

这是我遇到的一个面试问题:

你会得到一个国家城市之间的飞机地图,基本上是一个有向图,图的权重是城市之间飞机的成本。你还得到了一张单张优惠券,可以在任何一次航班上获得50%的优惠。找到在两个城市之间旅行的最低成本吗?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2014-08-10 16:15:46

这个问题的基本算法是Dijkstra的最短路径算法。然而,我们需要找到一种包括优惠券的方法。

我们可以通过引入优惠券状态来做到这一点。要么是available,要么是spent。在每个机场,政府可以两者兼而有之。因此,我们可以复制顶点的数量(对于机场)。对于每个机场,一个顶点将具有available状态,另一个顶点将具有spent状态。边缘必须稍微改变一下。从具有spent状态的顶点到具有available状态的顶点是不可能的。另一方面,原来的成本减半。

现在,我们希望找到从起始机场(具有available状态的顶点)到目标机场(具有spent状态的顶点)的最小成本路径。这可以通过Dijkstra的普通算法来实现。

票数 5
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/25230430

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档