参观博物馆的最低费用

Question

最近，我参加了一个招聘挑战，并看到了这个问题：

给出的N博物馆的地图与给定的入场费和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算法。

提前谢谢。

Answer 1

你的图形从“博物馆外”的节点开始，它们之间的边缘道路。

您需要如下所示的条目的优先级队列：

{
    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)

这应该在time O((n+m) log(n+m))中执行，n是博物馆的数量，m是道路的数量。