eolymp
bolt
Try our new interface for solving problems
Məsələlər

Поиск в ширину 0-1

Поиск в ширину 0-1

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Задан неориентированный граф. Вес его ребер может принимать только значения 0 или 1. Найдите кратчайшее расстояние между вершинами s и d.

Giriş verilənləri

Первая строка содержит четыре целых числа: количество вершин 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).

Çıxış verilənləri

Выведите кратчайший путь между вершинами s и d.

Nümunə

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
Müəllif Михаил Медведев