Con đường xen kẽ hai màu
Points
75
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Cho một đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh. Mỗi cạnh được tô một trong hai màu: 0 (đỏ) hoặc 1 (xanh).
Bạn cần đi từ đỉnh $1$ đến đỉnh $N$ sao cho không có hai cạnh liên tiếp nào trên đường đi có cùng màu. Hãy tìm độ dài (số cạnh) ngắn nhất của một lộ trình hợp lệ.
Dữ liệu vào
Dòng đầu chứa hai số nguyên $N, M$.
$M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, c$ ($c \in {0, 1}$) mô tả cạnh nối $u$ và $v$ có màu $c$.
Dữ liệu ra
In ra số cạnh ít nhất của đường đi hợp lệ từ $1$ đến $N$, hoặc -1 nếu không tồn tại đường đi.
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 2 0 2 3 1 3 4 0 1 4 1 |
1 |
| 4 3 1 2 0 2 3 0 3 4 1 |
-1 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le M \le 2 \cdot 10^5$
- $1 \le u, v \le N$, $c \in {0, 1}$
Community Discussion