Автор задачи: Константин Бац, разработчик: Мария Жогова
Рассмотрим путь раствора с отдельной точки халата, на которую он был нанесён.
По условию, длина этого пути — расстояние от этой вершины до ближайшей дырки. Поскольку вес любого ребра в нашем графе равен единице, то для поиска кратчайшего расстояния до любой дырки в таком графе можно использовать поиск в ширину (bfs).
Нам надо найти время, через которое халат высохнет, то есть раствор, нанесённый на каждую из начальных вершин дотечёт до каких-либо дырок. Заметим, что это равно максимальному значению среди минимальных расстояний, найденных выше.
Ограничения задачи не позволяли явно запустить поиск в ширину для каждой из начальных вершин. Однако можно было использовать один bfs для поиска всех расстояний сразу. Будем запускать алгоритм не из начальных точек, а из всех дырок в халате одновременно. Перед запуском поиска в ширину добавим в очередь все точки, из которых раствор вытекает, и скажем, что расстояние до них равно $$$0$$$. Тогда, когда алгоритм закончит свою работу, у нас будут посчитаны минимальные расстояния от ближайшей дырки до каждой вершины графа. Найдем максимальное посчитанное значение среди начальных вершин, это и будет ответом на задачу.
Итого, нам придется запустить один bfs, который работает за $$$\mathcal{O}(n + m)$$$, и еще несколько раз проитерироваться по массивам. Время работы такого решения — $$$\mathcal{O} (n + m)$$$.