algorithm - 参观博物馆的最低费用

我最近参加了一个招聘挑战，看到了这样一个问题：
给定具有给定入场费的博物馆地图和连接它们的加权双向道路从每个博物馆开始，我们至少要找到一个博物馆的最低参观成本。费用将加上道路重量和参观博物馆的入场费。
输入格式：

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是道路数量。

关于algorithm - 参观博物馆的最低费用，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58560595/