Штрафи#17

Штрафи (Editorial)

Розберемося, на яких саме дорогах стоїть ДАІ. За умовою це дороги, які «обминути не можна», — тобто такі, після видалення яких граф розпадається. У теорії графів це називається мостами.

Отже, розв'язок складається з двох кроків.

Крок 1: знайти всі мости. Це робиться класичним обходом у глибину з мітками (час входу) та (мінімальний час входу, досяжний з піддерева по зворотних ребрах). Ребро , де — нащадок, є мостом тоді й лише тоді, коли \mathrm{low}[v] > \mathrm{tin}[u]. Складність — \mathcal{O}(N + M).

Крок 2: знайти найдешевший маршрут. Призначимо кожному мосту вагу (стільки коштує штраф), а всім іншим дорогам — вагу . Тепер відповідь — це довжина найкоротшого шляху з міста у місто у такому зваженому графі.

Оскільки ваг лише дві, замість алгоритму Дейкстри можна скористатися 0-1 BFS із двобічною чергою, що дає \mathcal{O}(N + M). Дейкстра теж пройде за \mathcal{O}((N+M)\log N).

Якщо місто недосяжне з , шляху немає — виводимо .

Зверніть увагу, що маршрут не зобов'язаний бути найкоротшим за кількістю доріг: Степану вигідно робити гак, аби лише оминути зайвий міст.