Các đỉnh trên đường đi ngắn nhất
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Cho một đồ thị vô hướng không trọng số gồm $N$ đỉnh và $M$ cạnh, cùng hai đỉnh $S$ và $T$.
Một đỉnh $v$ được gọi là nằm trên đường đi ngắn nhất nếu tồn tại ít nhất một đường đi ngắn nhất từ $S$ đến $T$ đi qua đỉnh $v$ (tính cả $S$ và $T$). Hãy đếm số lượng đỉnh như vậy.
Dữ liệu vào
Dòng đầu chứa bốn số nguyên $N, M, S, T$.
$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả cạnh nối giữa $u$ và $v$.
Dữ liệu ra
In ra số lượng đỉnh nằm trên ít nhất một đường đi ngắn nhất từ $S$ đến $T$ (in 0 nếu không có đường đi nào từ $S$ đến $T$).
Ví dụ
| Input | Output |
|---|---|
| 5 6 1 5 1 2 2 5 1 3 3 5 1 4 4 3 |
4 |
| 4 2 1 4 1 2 3 4 |
0 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le M \le 2 \cdot 10^5$
- $1 \le S, T \le N$
Community Discussion