时间戳

首页 > 解决方案 > 参观博物馆的最低费用

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

问题描述

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

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号馆开始，我们可以参观4号馆，门票为2。

我需要比从图形的每个节点应用 dijsktra 更有效的优化方法。约束非常高，可以避免弗洛伊德 Warshall 算法。

提前致谢。

标签： algorithmdata-structuresgraph

解决方案

您的图表以“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的数量，是道路的数量。

推荐阅读