Вежа гномів (Розбір)

Побудуємо граф у вигляді списку суміжності $g$, де $g[i]$ містить пари чисел $(j,a)$ такі, що з предметів $i$ та $j$ можна сконструювати предмет $a$: (i, j) \to a.

Нехай $cost$ — масив, спочатку такий, що містить вартість покупки предметів (cost[i] = c_i). В кінці роботи алгоритму $cost[i]$ міститиме мінімальну кількість грошей, необхідну для отримання предмета $i$.

Спочатку всі предмети вважаються необробленими (used[i] = 0).

Поки існує принаймні один необроблений предмет:

• Знаходимо предмет $a$ з найменшою вартістю;

• Застосовуємо всі правила, перелічені в $g[a]$;

• Позначаємо предмет $a$ як оброблений: used[a] = 0;

Для кожного правила (a, b) \to to з $g[a]$ перераховуємо

Приклад

Розглянемо перший тест. Є $5$ предметів з такими вартістями їх покупки:

Є три правила конструювання предметів. Побудуємо на їх основі список суміжності.

Предмет $2$ має найменшу вартість cost[2] = 0. Застосовуємо всі правила, в яких бере участь предмет $2$, а саме ті, що перелічені в $g[2]$. Після цього позначаємо предмет $2$ як оброблений.

Наступним необробленим предметом з найменшою вартістю буде $3$. Застосовуємо правила, перелічені в $g[3]$. Вартість предметів при цьому не змінюється.

Далі необробленим предметом з найменшою вартістю стає предмет $4$. Застосовуємо правило з $g[4]$.

У подальших операціях вартість предметів не змінюється. Таким чином, мінімальна вартість отримання предмета $1$ дорівнює $2$.

Реалізація алгоритму

Оголосимо робочі масиви. Оголосимо список суміжності $g$, який міститиме правила конструювання предметів.

vector<int> cost, used;
vector<vector<pair<int, int>>> g;

Читаємо вхідні дані. Ініціалізуємо масиви.

scanf("%d %d", &n, &m);
g.resize(n + 1);
cost.resize(n + 1);
used.resize(n + 1);

Читаємо вартості покупки предметів.

for (i = 1; i <= n; i++)
  scanf("%d", &cost[i]);

Читаємо правила конструювання предметів і на їх основі будуємо список суміжності.

for (i = 0; i < m; i++)
{
  scanf("%d %d %d", &a, &x, &y);
  g[x].push_back(make_pair(y, a));
  g[y].push_back(make_pair(x, a));
}

Здійснюємо $n$ ітерацій.

for (k = 0; k < n; k++)
{

Серед необроблених предметів шукаємо той, у якого найменша вартість. Нехай це буде предмет з номером $a$.

  mn = 2e9; a = -1;
  for (i = 1; i <= n; i++)
    if (!used[i] && cost[i] < mn)
    {
      mn = cost[i];
      a = i;
    }

Позначаємо предмет $a$ як оброблений.

  used[a] = 1;

Перебираємо всі правила, в яких бере участь предмет $a$.

      for (auto x : g[a])
      {
         b = x.first;
         to = x.second; // (a, b) -> to
         if (cost[a] + cost[b] < cost[to]) cost[to] = cost[a] + cost[b];
  }
}

Виводимо мінімальну кількість грошей, необхідну для покупки першого предмета.

printf("%d\n", cost[1]);

Python реалізація

У Python $inf$ — це спеціальне значення, що позначає нескінченність. Воно доступне в модулі $math$ і для використання модуль необхідно імпортувати.

from math import inf

Читаємо вхідні дані.

n, m = map(int, input().split())
cost = [0] + list(map(int, input().split()))

Ініціалізуємо списки.

used = [False] * (n + 1)
g = [[] for _ in range(n + 1)]

Читаємо правила конструювання предметів і на їх основі будуємо список суміжності.

for _ in range(m):
  a, x, y = map(int, input().split())
  g[x].append((y, a))
  g[y].append((x, a))

Виконуємо $n$ ітерацій.

for k in range(n):

На кожній ітерації серед необроблених предметів шукаємо той, у якого найменша вартість. Нехай це буде предмет з номером $a$.

  mn = inf
  a = -1
  for i in range(1, n + 1):
    if not used[i] and cost[i] < mn:
      mn = cost[i]
      a = i

Позначаємо предмет $a$ як оброблений.

  used[a] = True

Перебираємо всі правила, в яких бере участь предмет $a$.

  for b, to in g[a]:
    if cost[a] + cost[b] < cost[to]:
       cost[to] = cost[a] + cost[b]

Виводимо мінімальну кількість грошей, необхідну для покупки першого предмета.

print(cost[1])