Các đỉnh trên đường đi ngắn nhất

General
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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$
Draft saved