Server#10456

Server (Editoryal)

Graf $1 0^{4}$ 10^4'e kadar köşe ve $4 \cdot 1 0^{4}$ 4 \cdot 10^4'e kadar kenar içerir, bu yüzden onu komşuluk listesi şeklinde saklayacağız. Tüm kenar ağırlıkları pozitiftir, dolayısıyla en kısa mesafeler Dijkstra algoritması ile bulunabilir.

Problemin graf terimleriyle ifade edilmesi. $a$ ve $b$ köşeleri arasındaki en kısa yolun uzunluğunu $d (a, b)$ ile gösterelim. Eğer sunucu $v$ şehrinde duruyorsa, $c_{i}$ c_i şehrinden gelen misafir $d (c_{i}, v)$ d(c_i, v) gecikmesini alır. Tüm misafirlerin toplam gecikmesi şuna eşittir

S (v) = d (c_{1}, v) + d (c_{2}, v) + ... + d (c_{k}, v)

S(v) = d(c_1, v) + d(c_2, v) + ... + d(c_k, v)

$S (v)$ değeri minimum olan köşeyi bulmak gerekir, eşitlik durumunda ise en küçük numaralı olanı.

Neden Dijkstra'yı misafirlerin şehirlerinden başlatıyoruz. Her aday $v$ köşesi için $v$ 'den Dijkstra çalıştırıp $k$ misafir şehrine olan mesafeleri toplayabilirdik. Ama aday sayısı $1 0^{4}$ 10^4'e kadar olabilir ve bu kadar çok çalıştırma fazla olur. Graf yönsüz olduğundan $d (c_{i}, v) = d (v, c_{i})$ d(c_i, v) = d(v, c_i) olduğuna dikkat edelim. Demek ki, $c_{i}$ c_i misafir şehrinden tek bir Dijkstra çalıştırması, sunucunun olası tüm yerleri için bu misafirin gecikmesini hemen verir. Misafir sayısı en fazla $100$ olduğundan, $k$ çalıştırma yeterlidir.

Toplamın nasıl biriktirildiği. Başlangıçta sıfırlarla doldurulmuş $s u m [1.. n]$ dizisini oluşturalım. $s u m [v]$ elemanı, sunucu $v$ köşesine yerleştirildiğinde misafirlerin toplam gecikmesini saklayacaktır.

Sonra her misafir için sırayla:

$c_{i}$ c_i köşesinden Dijkstra algoritmasını çalıştırıp $d i s t [1.. n]$ dist[1..n] dizisini elde ederiz, burada $d i s t [v] = d (c_{i}, v)$ dist[v] = d(c_i, v). Bu, sunucu $v$ şehrindeyse $i$ -inci misafirin gecikmesidir.
Tüm $v = 1, 2, ..., n$ v = 1, 2, ..., n köşelerini geziyoruz ve $s u m [v] + = d i s t [v]$ sum[v] += dist[v] işlemini gerçekleştiriyoruz. Böylece $i$ -inci misafirin katkısını sunucunun olası her yerleşim yerinin toplam gecikmesine ekliyoruz.

$k$ misafirin tamamı işlendikten sonra, her $s u m [v]$ elemanı tam olarak $k$ terim içerir — $v$ köşesine kadar olan tüm misafirlerin gecikmeleri, yani $s u m [v] = S (v)$ sum[v] = S(v).

Cevabın seçilmesi. Köşeleri $v = 1, 2, ..., n$ v = 1, 2, ..., n artan numara sırasıyla geziyoruz ve minimum toplama sahip köşeyi hatırlıyoruz. Cevabı yalnızca kesin eşitsizlik $s u m [v] < b es t$ sum[v] < best sağlandığında güncelliyoruz. Bu durumda aynı minimum toplama sahip birkaç köşe olduğunda, bunlardan ilki, yani en küçük numaralı olanı kalacaktır.

Minimum, yalnızca misafirlerin şehirleri arasında değil, tüm $n$ köşe arasında aranır: en uygun yer, misafir bulunmayan bir şehir olabilir.

Örnek

Örnekte verilen graf aşağıdaki gibidir:

Misafirlerin yaşadığı köşelerden Dijkstra algoritmasını çalıştıralım: $1, 2$ ve $5$ . Bu köşelerin her biri için diğer tüm şehirlere olan en kısa mesafeleri belirleyelim.

Sonra grafın her köşesi için misafirlerin bulunduğu tüm şehirlere olan mesafelerin toplamını bulalım. Minimum mesafe toplamı $13$ 'e eşittir ve bu, en küçük numaralı $2$ köşesinde elde edilir.

Böylece sunucu $2$ numaralı şehre yerleştirilmelidir. Ondan misafirlerin yaşadığı şehirlere olan toplam mesafe $5 + 0 + 8 = 13$ 5 + 0 + 8 = 13 olur.

Algoritmanın uygulanması

Sonsuzluk sabitini tanımlayalım.

#define INF 0x3F3F3F3F

$e d g e$ yapısı, kenar hakkındaki bilgiyi saklayacaktır: kenarın gittiği $n o d e$ köşesi ve bu kenarın $d i s t$ ağırlığı.

struct edge
{
  int node, dist;
  edge(int node, int dist) : node(node), dist(dist) {}
};

$(n o d e, d i s t)$ (node, dist) çiftlerini $d i s t$ değerinin azalan sırasına göre sıralamak için bir karşılaştırıcı tanımlayalım.

bool operator< (edge a, edge b)
{
  return a.dist > b.dist;
}

Grafı temsil etmek için komşuluk listesini tanımlayalım.

vector<vector<edge> > g;

Dijkstra fonksiyonu Dijkstra algoritmasını gerçekleştirir. Girdi olarak $g$ grafını ve $s t a r t$ başlangıç köşesini alır. Dönüş değeri $d$ dizisidir, burada $d [i]$ , $s t a r t$ köşesinden $i$ köşesine olan en kısa mesafeyi içerir.

void Dijkstra(vector<vector<edge> >& g, vector<int>& d, int start)
{
  priority_queue<edge> pq;
  pq.push(edge(start, 0));

  d = vector<int>(n + 1, INF);
  d[start] = 0;

  while (!pq.empty())
  {
    edge e = pq.top(); pq.pop();
    int v = e.node;

    if (e.dist > d[v]) continue;

    for (auto e : g[v])
    {
      int to = e.node;
      int cost = e.dist;
      if (d[v] + cost < d[to])
      {
        d[to] = d[v] + cost;
        pq.push(edge(to, d[to]));
      }
    }
  }
}

C++

Programın ana kısmı. Girdi verilerini okuyoruz.

scanf("%d %d %d", &n, &m, &k);
c.resize(k);
for (i = 0; i < k; i++)
  scanf("%d", &c[i]);

Girdi ağırlıklı grafını okuyoruz.

g.resize(n + 1);
for (i = 0; i < m; i++)
{
  scanf("%d %d %d", &a, &b, &w);
  g[a].push_back(edge(b, w));
  g[b].push_back(edge(a, w));
}

C++

Misafirlerin yaşadığı şehirlerden Dijkstra algoritmasını çalıştırıyoruz.

dp.resize(n + 1);
for (i = 0; i < k; i++)
{
  Dijkstra(g, dist, c[i]);

  for (j = 1; j <= n; j++)
   dp[j] += dist[j];
}

C++

Şu anda $d p [i]$ , $i$ köşesinden misafirlerin bulunduğu tüm şehirlere olan en kısa mesafelerin toplamını içermektedir. Geriye $d p$ dizisinin elemanları arasında minimum değeri bulmak ve buna karşılık gelen cevabı yazdırmak kalıyor. $pt r$ değişkeni, sunucunun yerleştirilmesi gereken en küçük köşe numarasını saklar.

res = INF;
for (i = 1; i <= n; i++)
{
  if (dp[i] < res)
  {
    res = dp[i];
    ptr = i;
  }
}

C++

Cevabı yazdırıyoruz.

printf("%d %d\n", ptr, dp[ptr]);