Cırtdanların Qalası (Həll təhlili)

G gəldikdə, $g[i]$ cütlüklərini $(j,a)$ ilə tutacaq şəkildə bir yaxınlıq siyahısı qrafı inşa edək ki, əgər $i$ və $j$ predmetləri ilə $a$ predmetini düzəldə bilsək: (i, j) \to a.

Gəlin $cost$ - əşyaların alış qiymətini ehtiva edən zərrəfi olsun (cost[i] = c_i). Alqoritmin sonunda $cost[i]$ $i$ əşyasının əldə edilməsi üçün lazım olan minimal pul miqdarını ehtiva edəcəkdir.

İlkin olaraq bütün əşyalar işlənməyən (neçə istifadə olunmayan) hesab olunur (used[i] = 0).

Heç olmasa bir işlənməyən əşya varkən:

• Ən az qiymətə sahib bir əşya $a$ tapırıq;

• $g[a]$də sadalanan bütün qaydaları tətbiq edirik;

• Əşyanı emal olunmuş kimi qeyd edin: used[a] = 0;

Hər bir qayda üçün (a, b) \to to $g[a]$dən qiymətləri yenidən hesablayırıq

Misal

Birinci testi nəzərdən keçirək. Alış qiymətlərinin belə olduğu $5$ əşya vardır:

Üç əşya qurma qaydası vardır. Bunlara əsasən bir yaxınlıq siyahısı inşa edək.

Əşya $2$ ən az qiymətə malikdir cost[2] = 0. Əşyası $2$ olan bütün qaydaları tətbiq edirik, yəni $g[2]$də sadalananlar. Bundan sonra, əşya $2$ emal olunmuş kimi qeyd edirik.

Növbəti işlənməyən ən az qiymətə sahib əşya $3$ olacaq. $g[3]$də sadalanan qaydaları tətbiq edirik. Bu müddətdə əşyaların qiymətləri dəyişməz.

Sonra işlənməyən ən az qiymətə sahib əşya $4$ olur. $g[4]$dən qaydanı tətbiq edirik.

Sonrakı əməliyyatlarda əşyaların qiymətləri dəyişməz. Beləliklə, əşya $1$in alınması üçün minimal qiymət $2$-yə bərabərdir.

Algoritmin realizasiyası

İşlək zərrəfləri elan edək. İdəntifikatorların qurma qaydalarını ehtiva edən bir yaxınlıq siyahısı $g$ elan edək.

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

Daxili məlumatları oxuyuruq. Zərrəfləri ilkləndiririk.

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

Əşyaların alış qiymətlərini oxuyuruq.

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

Əşyaların qurma qaydalarını oxuyuruq və yanaşmalarına əsaslanaraq yaxınlıq siyahısı hazırlayırıq.

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$ iterasiya etmək.

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

İşlənməyən əşyalar arasında ən az qiymətə sahib olanı axtarırıq. Gəl, bu $a$ sanıli əşyası olsun.

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

Əşyası $a$ işlənmiş kimi qeyd edirik.

  used[a] = 1;

Əşyası $a$ olan bütün qaydaları təkrarlayın.

      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];
  }
}

Birinci əşya üçün lazim olan minimal pul miqdarını çıxarırıq.

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

Python reallaşdırılması

Python-da $inf$ sonsuzluğu ifadə edən xüsusi bir dəyərdir. O, $math$ modulunda mövcuddur və istifadə üçün məzmun edilə bilər.

from math import inf

Daxili məlumatları oxuyuruq.

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

Siyahıları ilkləndiririk.

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

Əşyaların qurma qaydalarını oxuyuruq və yaxınlıq siyahısını qururuq.

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

$n$ iterasiya edirik.

for k in range(n):

Hər məsələnin iterasiyaslarında işlənməyən əşyalar arasında ən az qiymətə sahib olanı axtarırıq. Gəl, bu $a$ olan bir nömrəli əşyadır.

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

Əşyası $a$ işlənmiş kimi qeyd edirik.

  used[a] = True

Əşyası $a$ olan bütün qaydaları təkrarlayın.

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

Birinci əşya üçün lazim olan minimal pul miqdarını çıxarırıq.

print(cost[1])