Задачі
Пошук у ширину 0-1
Пошук у ширину 0-1
Дано неорієнтований граф. Вага його ребер може приймати тільки значеня $0$ або $1$. Знайдіть найкоротшу відстань між вершинами $s$ і $d$.
\InputFile
Перший рядок містить чотири цілих числа: кількість вершин $n$, кількість ребер $m\:(n, m \le 10^5)$ і номери вершин $s$ і $d\:(1 \le s, d \le n)$. Кожен з наступних $m$ рядків містить три цілих числа $a, b$ і $w$ що задають неорієнтоване ребро $(a, b)$ з цілочисельною вагою $w\:(0 \le w \le 1)$.
\OutputFile
Виведіть найкоротший шлях між вершинами $s$ і $d$.
\includegraphics{https://static.e-olymp.com/content/d4/d41a7d95d5084f6f627f76bd21b509b9458b00b1.gif}
Вхідні дані #1
5 5 1 3 1 2 0 2 3 1 3 4 0 4 5 1 1 5 1
Вихідні дані #1
1