Server#10456

Server (Editorial)

El grafo contiene hasta $1 0^{4}$ 10^4 vértices y hasta $4 \cdot 1 0^{4}$ 4 \cdot 10^4 aristas, por lo que lo almacenaremos en forma de lista de adyacencia. Todos los pesos de las aristas son positivos, por lo tanto, las distancias más cortas se pueden encontrar mediante el algoritmo de Dijkstra.

Planteamiento del problema en términos de grafos. Denotemos por $d (a, b)$ la longitud del camino más corto entre los vértices $a$ y $b$ . Si el servidor se ubica en la ciudad $v$ , entonces el invitado de la ciudad $c_{i}$ c_i recibe un retraso $d (c_{i}, v)$ d(c_i, v). El retraso total de todos los invitados es igual a

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)

Hay que encontrar el vértice $v$ con el valor mínimo de $S (v)$ , y en caso de empate, el de menor número.

Por qué ejecutamos Dijkstra desde las ciudades de los invitados. Se podría ejecutar Dijkstra desde cada vértice candidato $v$ y sumar las distancias a los $k$ ciudades de los invitados. Pero hay hasta $1 0^{4}$ 10^4 candidatos, y tal cantidad de ejecuciones sería excesiva. Notemos que el grafo es no dirigido, por lo que $d (c_{i}, v) = d (v, c_{i})$ d(c_i, v) = d(v, c_i). Esto significa que una sola ejecución de Dijkstra desde la ciudad del invitado $c_{i}$ c_i proporciona de inmediato el retraso de ese invitado para todos los posibles lugares del servidor. Como hay a lo sumo $100$ invitados, bastan $k$ ejecuciones.

Cómo se acumula la suma. Creemos un arreglo $s u m [1.. n]$ , inicialmente lleno de ceros. El elemento $s u m [v]$ almacenará el retraso total de los invitados si el servidor se coloca en el vértice $v$ .

A continuación, para cada invitado, por turno:

Ejecutamos el algoritmo de Dijkstra desde el vértice $c_{i}$ c_i y obtenemos el arreglo $d i s t [1.. n]$ dist[1..n], donde $d i s t [v] = d (c_{i}, v)$ dist[v] = d(c_i, v). Este es el retraso del $i$ -ésimo invitado si el servidor está en la ciudad $v$ .
Recorremos todos los vértices $v = 1, 2, ..., n$ v = 1, 2, ..., n y realizamos $s u m [v] + = d i s t [v]$ sum[v] += dist[v]. De esta manera añadimos la contribución del $i$ -ésimo invitado al retraso total de cada posible ubicación del servidor.

Después de procesar a los $k$ invitados, cada elemento $s u m [v]$ contiene exactamente $k$ sumandos — los retrasos de todos los invitados hasta el vértice $v$ , es decir, $s u m [v] = S (v)$ sum[v] = S(v).

Elección de la respuesta. Recorremos los vértices $v = 1, 2, ..., n$ v = 1, 2, ..., n en orden creciente de números y guardamos el vértice con la suma mínima. Actualizamos la respuesta solo cuando se cumple la desigualdad estricta $s u m [v] < b es t$ sum[v] < best. De este modo, si hay varios vértices con la misma suma mínima, quedará el primero de ellos, es decir, el de menor número.

El mínimo se busca entre todos los $n$ vértices, no solo entre las ciudades de los invitados: el lugar óptimo puede resultar ser una ciudad donde no hay invitados.

Ejemplo

El grafo presentado en el ejemplo tiene el siguiente aspecto:

Ejecutemos el algoritmo de Dijkstra desde los vértices donde viven los invitados: $1, 2$ y $5$ . Para cada uno de estos vértices determinemos las distancias más cortas hasta todas las demás ciudades.

Luego, para cada vértice del grafo, encontremos la suma de las distancias hasta todas las ciudades con invitados. La suma mínima de distancias es igual a $13$ , y se alcanza en el vértice con el menor número $2$ .

Por lo tanto, el servidor debe colocarse en la ciudad $2$ . La distancia total desde allí hasta las ciudades donde viven los invitados es $5 + 0 + 8 = 13$ 5 + 0 + 8 = 13.

Implementación del algoritmo

Declaremos la constante infinito.

#define INF 0x3F3F3F3F

La estructura $e d g e$ almacenará información sobre la arista: el vértice $n o d e$ al que conduce la arista, y el peso $d i s t$ de esa arista.

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

Declaremos un comparador para ordenar los pares $(n o d e, d i s t)$ (node, dist) en orden decreciente del valor $d i s t$ .

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

Declaremos una lista de adyacencia para representar el grafo.

vector<vector<edge> > g;

La función Dijkstra implementa el algoritmo de Dijkstra. Recibe como entrada el grafo $g$ y el vértice inicial $s t a r t$ . El valor de retorno es el arreglo $d$ , donde $d [i]$ contiene la distancia más corta desde el vértice $s t a r t$ hasta el vértice $i$ .

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++

Parte principal del programa. Leemos los datos de entrada.

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

Leemos el grafo ponderado de entrada.

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++

Ejecutamos el algoritmo de Dijkstra desde las ciudades donde viven los invitados.

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++

En este momento, $d p [i]$ contiene la suma de las distancias más cortas desde el vértice $i$ hasta todas las ciudades donde se encuentran los invitados. Queda encontrar el valor mínimo entre los elementos del arreglo $d p$ y mostrar la respuesta correspondiente. La variable $pt r$ almacena el menor número de vértice en el que se debe colocar el servidor.

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

C++

Mostramos la respuesta.

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