Hành trình của hai robot
Points
80
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Trên một đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh, có hai robot đang đứng ở hai đỉnh phân biệt $S_1$ và $S_2$. Robot $1$ cần đi tới đỉnh $T_1$, robot $2$ cần đi tới đỉnh $T_2$.
Trong mỗi giây, cả hai robot bắt buộc phải đồng thời di chuyển sang một đỉnh kề theo một cạnh. Để tránh va chạm, tại bất kỳ thời điểm nào:
- Hai robot không được đứng cùng một đỉnh.
- Hai robot không được đi ngược chiều nhau trên cùng một cạnh trong cùng một giây (tức không được đổi chỗ trực tiếp cho nhau).
Hãy tìm thời gian ngắn nhất để hai robot đồng thời có mặt tại $T_1$ và $T_2$.
Dữ liệu vào
Dòng đầu chứa hai số nguyên $N, M$.
Dòng thứ hai chứa bốn số nguyên $S_1, T_1, S_2, T_2$.
$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả cạnh vô hướng giữa $u$ và $v$.
Dữ liệu ra
In ra số giây ngắn nhất để hai robot cùng tới đích, hoặc -1 nếu không thể.
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 4 4 1 1 2 2 4 1 3 3 4 |
2 |
| 3 2 1 3 3 1 1 2 2 3 |
-1 |
Giới hạn
- $2 \le N \le 40$
- $0 \le M \le N(N-1)/2$
- $1 \le S_1, T_1, S_2, T_2 \le N$, $S_1 \ne S_2$
Community Discussion