Đường đi đẹp nhất

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho đồ thị có hướng \(G=(V,E)\) gồm \(N\) đỉnh và \(M\) cung, \(s\)\(t\) là hai đỉnh của đồ thị \(G\). Một dãy các đỉnh \(P=\langle p_0=s, p_1, p_2, \dots, p_k=t \rangle\) sao cho \((p_{i_1}, p_i) \in E\), được gọi là 1 đường đi từ \(s\) đến \(t\). Một đường đi đơn giản (còn gọi là đường đi đơn) nếu tất cả các đỉnh trên đường đi đôi một khác nhau.
Biết rằng tồn tại ít nhất một đường đi từ s tới t, hãy chỉ ra đường đi đơn có thứ tự từ điển nhỏ nhất.

Input

  • Dòng đầu chứa các số nguyên \(N\), \(M\), đỉnh xuất phát \(s\), đỉnh cần đến \(t\).
  • \(M\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(u,v\) \((1 \leq u,v \leq N)\), thể hiện cho 1 cung nối từ đỉnh \(u\) đến đỉnh $v trong đồ thị.

Output

  • Ghi ra trên một dòng các đỉnh theo đúng thứ tự trên đường đi tìm được, bắt đầu từ đỉnh \(s\), kết thúc ở đỉnh \(t\) theo thứ tự từ điển nhỏ nhất.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3, M \leq 10^4\)
  • Subtask \(2\) (\(70\%\) số điểm): \(N \leq 10^5, M \leq 10^6\)

Example

Test 1

Input
8 12 1 8
1 2
1 3
2 3
2 4
3 1
3 5
3 7
4 6
6 2
6 8
7 8
7 6 
Output
1 2 3 7 6 8

Bình luận

Không có bình luận nào.