我最近参加了一次招聘挑战,看到了这个问题:
给定 N
个博物馆的 map ,给定入场费和连接它们的 M
加权双向道路。从每个博物馆开始,我们需要找到至少参观一个博物馆的最低成本。 费用将加上所走道路的权重和参观博物馆的入场费。
输入格式:
Number of museums N and number of roads M
Entry fees of each museum
Next M lines will have x, y, z where museum x and museum y are connected by road with weight z
输出格式:
N integers where ith integer denotes minimum cost to reach and enter any museum starting from ith museum.
输入:
5 4
1 2 3 1 5
1 2 1
2 3 1
3 4 1
4 5 1
输出:
1 2 2 1 2
在这里,从博物馆1开始,我们可以直接参观博物馆1,门票为1。 从博物馆 3 开始,我们可以以 2 的费用参观博物馆 4。
我需要比从图形的每个节点应用 dijsktra 更有效的优化方法。约束足够高以避免 floyd warshall 算法。
提前致谢。
最佳答案
您的图表以“X 博物馆外部”的节点和它们之间的边缘道路开始。
您需要一个条目的优先级队列,如下所示:
{
cost: xxx,
outside_museum: xxx
}
您使用如下所示的条目对其进行初始化:
{
cost: entry_fee_for_museum_x,
outside_museum: x
}
保留一个字典将博物馆映射到最低成本,命名为 cost_to_museum
。
现在你的循环看起来像这样:
while queue not empty:
get lowest cost item from queue
if it's museum is not in cost_to_museum:
cost_to_museum[item.outside_museum] = item.cost
for each road connecting to museum:
add to queue an entry for traveling to here from there
(That is, location is the other museum, cost is road + current cost)
这应该及时执行 O((n+m) log(n+m))
其中 n
是博物馆的数量,m
是路数。
关于algorithm - 参观博物馆的最低费用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58560595/