Đường đi ngắn nhất có thứ tự từ điển nhỏ 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. 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$
Community Discussion