Đường đi ngắn nhất có thứ tự từ điển nhỏ 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. Trong tất cả các đường đi ngắn nhất từ đỉnh $S$ đến đỉnh $T$, hãy tìm đường đi có thứ tự từ điển nhỏ nhất (so sánh dãy chỉ số các đỉnh đi qua từ đầu đến cuối).

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

Nếu không thể đi từ $S$ đến $T$, in ra -1. Ngược lại, in ra dãy các đỉnh trên đường đi ngắn nhất có thứ tự từ điển nhỏ nhất, cách nhau bởi dấu cách.

Ví dụ
Input Output
5 6 1 5
1 3
1 2
2 5
3 5
1 4
4 5
1 2 5
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 S, T \le N$
Draft saved