1. Идея

Нужно для каждого пункта найти расстояние до ближайшего склада по взвешенному неориентированному графу.

Если бы склад был только один, задача решалась бы обычным алгоритмом Дейкстры из одной вершины. Но складов несколько, и для каждой вершины нужен минимум по всем этим источникам.

Ключевая идея: запустить Дейкстру сразу из всех складов.

Для этого:

• всем вершинам-складам присваиваем расстояние 0;
• кладём их все в очередь с приоритетом;
• дальше работаем как в обычной Дейкстре.

Тогда алгоритм сам найдёт для каждой вершины минимальное расстояние от любого склада.

2. Наблюдения

1. Граф взвешенный, веса дорог неотрицательные: w >= 0.

   Это важное условие, потому что алгоритм Дейкстры корректно работает именно при неотрицательных весах.

2. Дороги двусторонние.

   Значит, каждое ребро u v w нужно добавить в обе стороны:

   • из u в v,
   • из v в u.

3. Если в вершине уже есть склад, ответ для неё равен 0.

   Это естественно учитывается в multi-source Дейкстре: такие вершины изначально получают расстояние 0.

4. Если какая-то вершина не достижима ни из одного склада, её расстояние так и останется бесконечным.

   Для таких вершин надо вывести -1.

5. Запускать Дейкстру отдельно от каждого склада нельзя.

   Если складов много, это было бы слишком медленно:

   • один запуск Дейкстры стоит примерно O((n + m) log n),
   • а запусков k,
   • итог может стать слишком большим.

   Поэтому нужен именно один общий запуск от всех складов.

3. Алгоритм

1. Считываем n, m.
2. Считываем список складов.
3. Строим список смежности графа.
4. Создаём массив dist, где:
   • dist[v] — минимальное известное расстояние от ближайшего склада до вершины v;
   • сначала все значения равны очень большому числу INF.
5. Создаём очередь с приоритетом pq.

6. Для каждого склада s:

   • ставим dist[s] = 0,
   • добавляем пару (0, s) в pq.

7. Пока очередь не пуста:

   • берём вершину v с минимальным текущим расстоянием d;
   • если d != dist[v], это устаревшая запись, пропускаем её;
   • иначе перебираем все рёбра v -> to веса w;
   • если d + w < dist[to], улучшаем:
     • dist[to] = d + w,
     • кладём (dist[to], to) в очередь.

8. После завершения:

   • если dist[i] осталось равным INF, выводим -1;
   • иначе выводим dist[i].

4. Почему это работает

Разберём, почему multi-source Дейкстра действительно находит расстояния до ближайшего склада.

4.1. Что означает инициализация всех складов нулями

Мы как будто добавили в граф новую фиктивную вершину S и соединили её рёбрами веса 0 со всеми складами.

Тогда задача "найти расстояние от ближайшего склада до вершины v" превращается в задачу "найти кратчайшее расстояние от S до v".

Почему?

• из S можно попасть в любой склад за 0,
• дальше идти по дорогам графа,
• значит, путь из S до v — это просто путь от какого-то склада до v,
• минимальный такой путь и есть расстояние до ближайшего склада.

Но явно добавлять вершину S не нужно. Достаточно просто сразу поместить все склады в очередь с расстоянием 0. Это полностью эквивалентно.

4.2. Почему Дейкстра остаётся корректной

Все веса дорог неотрицательны. Значит, стандартное свойство Дейкстры сохраняется:

• когда вершина извлекается из очереди с расстоянием d,
• и это значение совпадает с dist[v],
• то d уже является окончательным кратчайшим расстоянием.

Так как в начале в очереди стоят все склады с нулевыми расстояниями, волна релаксаций распространяется сразу от всех источников. В итоге каждая вершина получает минимальную стоимость пути от любого из них.

4.3. Почему недостижимые вершины получают -1

Если из складов нельзя дойти до некоторой вершины, то ни одна релаксация её не затронет. Значит, её значение в dist останется равным INF. Такие вершины по условию нужно выводить как -1.

5. Сложность

Пусть:

• n — число вершин,
• m — число дорог.

Тогда:

• построение графа занимает O(m);
• алгоритм Дейкстры работает за O((n + m) log n).

Итоговая сложность:

• O((n + m) log n).

Память:

• граф хранит 2m направленных ребер, потому что дороги двусторонние;
• массив расстояний и очередь дают суммарно O(n + m) памяти.

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int k;
    cin >> k;
    vector<int> warehouses(k);
    for (int i = 0; i < k; i++) {
        cin >> warehouses[i];
    }

    vector<vector<pair<int, int>>> graph(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    const long long INF = numeric_limits<long long>::max() / 4;
    vector<long long> dist(n + 1, INF);

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    for (int s : warehouses) {
        if (dist[s] > 0) {
            dist[s] = 0;
            pq.push({0, s});
        }
    }

    while (!pq.empty()) {
        long long d = pq.top().first;
        int v = pq.top().second;
        pq.pop();

        if (d != dist[v]) {
            continue;
        }

        for (auto edge : graph[v]) {
            int to = edge.first;
            int w = edge.second;
            long long nd = d + w;
            if (nd < dist[to]) {
                dist[to] = nd;
                pq.push({nd, to});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) {
            cout << -1;
        } else {
            cout << dist[i];
        }
        if (i < n) {
            cout << ' ';
        }
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

import heapq

n, m = map(int, input().split())

line = list(map(int, input().split()))
k = line[0]
warehouses = line[1:]

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))

INF = 10**30
dist = [INF] * (n + 1)
pq = []

for s in warehouses:
    if dist[s] > 0:
        dist[s] = 0
        heapq.heappush(pq, (0, s))

while pq:
    d, v = heapq.heappop(pq)
    if d != dist[v]:
        continue

    for to, w in graph[v]:
        nd = d + w
        if nd < dist[to]:
            dist[to] = nd
            heapq.heappush(pq, (nd, to))

answer = []
for i in range(1, n + 1):
    if dist[i] == INF:
        answer.append("-1")
    else:
        answer.append(str(dist[i]))

print(" ".join(answer))