Đường đi ngắn nhất giữa hai trạm
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Hệ thống tàu điện ngầm gồm $N$ nhà ga đánh số từ $1$ đến $N$ và $M$ tuyến đường hai chiều kết nối trực tiếp giữa các cặp nhà ga. Mỗi tuyến đường mất đúng $1$ phút để di chuyển.
Hãy tìm thời gian ngắn nhất (tính bằng phút) để đi từ nhà ga $S$ đến nhà ga $T$, hoặc cho biết không thể đi tới được.
Dữ liệu vào
Dòng đầu tiên chứa bốn số nguyên $N, M, S, T$ ($1 \le S, T \le N$).
$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả một tuyến đường hai chiều nối ga $u$ và ga $v$.
Dữ liệu ra
In ra một số nguyên duy nhất là số phút ngắn nhất để đi từ $S$ đến $T$. Nếu không thể đến $T$, in ra -1.
Ví dụ
| Input | Output |
|---|---|
| 5 5 1 5 1 2 2 3 3 5 1 4 4 5 |
2 |
| 4 2 1 4 1 2 3 4 |
-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$
Community Discussion