Пожарные части
В городе n перекрёстков, m двусторонних улиц известной длины и k пожарных частей, каждая на своём перекрёстке. Городская служба хочет знать, насколько далеко от каждого перекрёстка до ближайшей части по дорогам: это расстояние почти напрямую превращается во время, за которое приедет машина.
Для каждого перекрёстка выведите расстояние до ближайшей пожарной части. В одном из тестов это настоящий Алматы, но части поставлены в случайные места — не ищите в ответе адреса настоящих депо.
Вход
В первой строке n, m, k (1 ≤ n ≤ 50 000, 0 ≤ m ≤ 100 000, 1 ≤ k ≤ n). Дальше m строк a b w — улица длиной w (1 ≤ w ≤ 10 000). В последней строке k номеров перекрёстков с пожарными частями; номера могут повторяться.
Выход
Одна строка из n чисел через пробел: для перекрёстка v = 1, 2, …, n — расстояние до ближайшей части или -1, если ни до одной не доехать.
Примеры
Пример 1
7 8 2 1 2 4 2 3 3 3 4 5 4 5 2 5 6 6 6 7 1 2 6 10 3 7 8 1 5
0 4 7 2 0 6 7
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Можно запустить Дейкстру из каждой части и взять минимум. Сколько это будет стоить, если частей две тысячи, а перекрёстков пятьдесят тысяч?
2Подсказка 2
Представьте, что все части соединены с одним воображаемым перекрёстком улицами нулевой длины. Что тогда означает кратчайшее расстояние от этого воображаемого перекрёстка?
3Идея
Добавим фиктивную вершину-исток и соединим её со всеми частями рёбрами длины 0. Расстояние от истока до v — это ровно расстояние от v до ближайшей части. Значит, хватит одного запуска Дейкстры. А фиктивную вершину даже не нужно заводить: её единственный шаг — положить все части в кучу с расстоянием 0. Это называется поиск от нескольких источников.
4Разбор
Читаем граф. Для каждой части ставим dist[s] = 0 и кладём её в кучу (повторы пропускаем). Дальше обычный алгоритм Дейкстры до опустошения кучи, без раннего выхода: ответ нужен для всех вершин. Вершины, до которых так и не дошли, печатаем как −1.
Волна теперь стартует сразу из всех частей и растёт одновременно вокруг каждой. Перекрёсток достаётся той части, чья волна дошла до него первой, — это и есть ближайшая часть. Заодно можно запомнить, какая именно: так строится разбиение города на зоны ответственности, дорожный аналог диаграммы Вороного.
4+Решение
5Сложность
Один проход Дейкстры: O((n + m) log n) независимо от числа частей. Отдельный запуск из каждой части стоил бы в k раз больше — при k = 2000 это разница между долей секунды и часом.
6Типичные ошибки
- Дейкстра из каждой части. Ответы правильные, но тест с двумя тысячами частей не уложится во время.
- Поиск от каждого перекрёстка до частей. Ещё хуже: n запусков вместо k.
- Ранний выход. В задаче про один финиш мы останавливались, достав финиш из кучи. Здесь финишей нет — нужны все расстояния.
- Повторяющиеся части. Если один номер встречается дважды, ничего страшного, но не кладите его в кучу двести раз — это лишние операции.