Нас цікавить не відстань між конкретною парою вершин, а мінімум по всіх учасниках відстані до найближчого стільця. Тому запускати Дейкстру з кожного учасника окремо не потрібно — достатньо однієї багатоджерельної Дейкстри.
Ідея: покладемо в чергу з пріоритетами одразу всі вершини зі стільцями (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}.