Минимальная стоимость посещения музея

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Мы можем посетить музей 4 со стоимостью 2.

Мне нужен эффективный оптимизированный подход, чем применение dijsktra из каждого узла графа. Ограничения достаточно высоки, чтобы избежать алгоритма Флойда Уорсхолла.

Заранее спасибо.

Answer 1

Ваш график начинается с узлов «вне Музея 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 - это количество дорог.