Məsələlər
Поиск в ширину 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}
Giriş verilənləri #1
5 5 1 3 1 2 0 2 3 1 3 4 0 4 5 1 1 5 1
Çıxış verilənləri #1
1