Нас цікавить не відстань між конкретною парою аудиторій, а мінімум по всіх лекційних аудиторіях відстані до найближчого буфету. Тому запускати Дейкстру з кожної лекційної окремо не потрібно — достатньо однієї багатоджерельної Дейкстри.
Ідея проста: додамо у чергу з пріоритетами одразу всі аудиторії з буфетами (a_i = 2) з нульовою відстанню. Тоді після роботи алгоритму дорівнюватиме відстані від до найближчого буфету — граф неорієнтований, тому напрямок ролі не грає.
Щоб знати не лише відстань, а й сам буфет, разом із відстанню зберігатимемо для кожної вершини «джерело» — номер буфету, з якого прийшло поточне найкраще значення. При релаксації ребра джерело копіюється від сусіда.
Після цього перебираємо всі лекційні аудиторії (a_i = 1) і вибираємо ту, у якої найменша. Виводимо номер цієї аудиторії, її буфет-джерело та саму відстань. Якщо жодна лекційна не має скінченної відстані, виводимо .
Складність — \mathcal{O}((N + M) \log N), чого достатньо при N \le 5000 і M \le 10^5. Відстані підсумовуються, тому беріть 64-бітний тип і «нескінченність» на кшталт 10^{18}.
Окремо зауважте, що аудиторія може бути одночасно початком і кінцем лише якщо вона й лекційна, і буфет одночасно, — за умовою a_i приймає лише одне значення, тому такого не буває.