Гра зi стiльцями#146

Гра зi стiльцями (Editorial)

Нас цікавить не відстань між конкретною парою вершин, а мінімум по всіх учасниках відстані до найближчого стільця. Тому запускати Дейкстру з кожного учасника окремо не потрібно — достатньо однієї багатоджерельної Дейкстри.

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

Щоб знати не лише відстань, а й сам стілець, разом із відстанню зберігатимемо для кожної вершини «джерело» — номер стільця, з якого прийшло поточне найкраще значення. Під час релаксації ребра джерело копіюється від сусіда.

Далі перебираємо всі вершини з учасниками (A_i = 1) і вибираємо ту, у якої найменша. Виводимо номер цієї вершини, її стілець-джерело та саму відстань. Якщо жоден учасник не має скінченної відстані, виводимо .

Складність — \mathcal{O}((N + M) \log N), чого достатньо при N \le 7 \cdot 10^4 і M \le 2 \cdot 10^5.

Дві деталі. По-перше, ваги ребер можуть дорівнювати нулю — це не заважає Дейкстрі. По-друге, відстані підсумовуються до 2 \cdot 10^5 \cdot 10^5 = 2 \cdot 10^{10}, тому беріть 64-бітний тип і «нескінченність» на кшталт 10^{18}.