Розберемося, на яких саме дорогах стоїть ДАІ. За умовою це дороги, які «обминути не можна», — тобто такі, після видалення яких граф розпадається. У теорії графів це називається мостами.
Отже, розв'язок складається з двох кроків.
Крок 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).
Якщо місто недосяжне з , шляху немає — виводимо .
Зверніть увагу, що маршрут не зобов'язаний бути найкоротшим за кількістю доріг: Степану вигідно робити гак, аби лише оминути зайвий міст.