CJ thanh toán BALLAS

Xem PDF

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

Khu vực SAN ANDREAS\(N\) ngôi nhà và \(M\) đường giao thông một chiều. Mỗi con đường kết nối trực tiếp giữa 2 ngôi nhà. Các ngôi nhà được đánh số từ \(1\) tới \(N\). CJ đang chuẩn bị thanh toán nhóm BALLAS ở một ngôi nhà trong khu vực, và sẽ bắt đầu tại nhà của CJ. Nhà của CJ có chỉ số là \(s\), nhà của nhóm BALLAS có chỉ số là \(t\). Một đường đi gọi là đường đi đơn nếu trong quá trình đi từ nhà CJ tới nhà của nhóm BALLAS, tất cả ngôi nhà đi qua nhiều nhất một lần. Và tồn tại ít nhất một đường đi từ \(s\) tới \(t\) (vì thế CJ mới có thể đi thanh toán được).

Hãy tìm cho CJ đường đi đơn ngắn nhất để CJ nhanh chóng thanh toán nhóm BALLAS càng nhanh càng tốt (CJ còn nhiều việc chưa giải quyết xong). Nếu có nhiều đường đi đơn ngắn nhất, thì chỉ ra đường đi có thứ tự từ điển nhỏ nhất trong số đó.

Input

  • Dòng đầu tiên chứa 4 số nguyên dương \(N,M,s,t \ (1 \leq s, t \leq N, s \ne t)\).
  • \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v \ (1 \leq u, v \leq N, u \ne v)\) thể hiện có đường đi một chiều nối từ ngôi nhà \(u\) tới ngôi nhà \(v\) trong khu vực.

Output

  • Ghi ra trên một dòng các ngôi nhà theo đúng thứ tự trên đường đi ngắn nhất tìm được, bắt đầu từ ngôi nhà \(s\), kết thúc ở ngôi nhà \(t\) theo thứ tự từ điển nhỏ nhất (Ví dụ \(10\) có thứ tự từ điển lớn hơn \(5\), \(5\) có thứ tự từ điển lớn hơn \(1\)).

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 3
3 5
7 6
1 2
2 4
2 3
3 1
3 7
6 8
4 6
6 2
7 8 
Output
1 3 7 8
Note


Bình luận


  • 7
    jumptozero 3:07 p.m. 30 Tháng 5, 2021

    Mình xin chia sẻ lời giải bài này :

    • Ý tưởng của bài này là sự kết hợp của bài BFS Cơ bản và truy vết. Nhưng trước tiên ta phải sắp xếp lại thứ tự đỉnh kể theo thứ tự tăng dần để đảm bảo đường đi in ra theo thứ tự từ điển

    Như vậy là bài toán đã được giải quyết xong, các bạn có thể tham khảo code tại đây: Link