Giải chạy marathon
Đề bài
Mô tả
Năm nay, một kỳ thi ICPC khu vực sẽ được tổ chức tại Hà Nội. Bên cạnh cuộc thi rất khó để chọn ra các đội vào chung kết thế giới, ban tổ chức quyết định tổ chức thêm một giải chạy marathon để các thí sinh có dịp khám phá vẻ đẹp của Hà Nội.
Địa điểm tổ chức giải marathon gồm nút giao, đánh số từ đến . Có con đường hai chiều, đánh số từ đến ; con đường thứ nối hai nút giao và và có độ dài . Các con đường đảm bảo luôn đi được giữa mọi cặp nút giao.
Giải marathon gồm nhiều lượt chạy. Trong mỗi lượt, các vận động viên xuất phát ở một nút giao, chạy qua một số con đường và về đích ở một nút giao khác. Mọi vận động viên chạy cùng một lộ trình do ban tổ chức chọn. Các điều kiện sau đúng với mọi lượt:
- Có ít nhất một lượt chạy.
- Trong mọi lượt, nút xuất phát khác nút về đích.
- Nút xuất phát của mỗi lượt trùng với nút về đích của lượt trước đó.
- Trong mọi lượt, ban tổ chức luôn chọn một đường đi ngắn nhất từ nút xuất phát đến nút về đích. Đường đi ngắn nhất là đường đi có tổng độ dài các con đường nhỏ nhất có thể.
Ban tổ chức định nghĩa tập độ khó của giải là tập các giá trị phân biệt của độ dài các lượt chạy. Cụ thể, một giải gồm lượt có thể biểu diễn bằng dãy nút giao , trong đó lượt thứ xuất phát ở và về đích ở . Gọi là độ dài đường đi ngắn nhất từ nút đến nút . Tập độ khó của giải là tập các giá trị xuất hiện ít nhất một lần trong dãy .
Để giải thêm thú vị, ban tổ chức có phương án. Mỗi phương án là một tập số , và ban tổ chức muốn biết có thể tổ chức một giải có tập độ khó đúng bằng tập này hay không.
Hãy giúp ban tổ chức có một kỳ thi ICPC thật tuyệt vời!
Dữ liệu vào
Dòng đầu tiên chứa số nguyên , số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ có dạng:
- Dòng đầu tiên là một dòng trống.
- Dòng thứ hai chứa ba số nguyên , , (, , ): số nút giao, số con đường và số phương án.
- dòng tiếp theo, dòng thứ chứa ba số nguyên , , (, ) mô tả con đường thứ .
- dòng cuối, mỗi dòng chứa số nguyên () và theo sau là số nguyên () mô tả một phương án.
Dữ liệu đảm bảo:
- Tổng trên mọi bộ dữ liệu không vượt quá .
- Tổng trên mọi phương án của mọi bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một dòng gồm đúng từ. Từ thứ là câu trả lời cho phương án thứ : Yes nếu có thể tổ chức được giải như vậy, No nếu không.
Ràng buộc
- , , ; mọi cặp nút giao đều đi được đến nhau.
- , , .
- Tổng không vượt quá , tổng không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 5 4 3 3 4 1 2 1 2 3 2 3 4 5 4 2 1 2 2 3 4 3 3 4 8 5 4 3 3 4 1 2 1 2 3 2 3 4 5 4 2 4 6 2 3 5 3 4 5 6 |
No Yes Yes Yes Yes Yes |
Bộ thứ nhất, phương án 2: giải có , . Phương án 3: giải có , , . Phương án 1: chỉ có cặp cách nhau và cặp cách nhau , không nối tiếp được. |
| 3 1 0 3 1 1 2 1 2 1 10000000 3 3 3 1 2 1 2 3 1 1 3 1 1 1 1 2 2 1 2 3 2 4 1 2 1 2 3 1 1 1 1 2 2 1 2 1 3 |
No No No Yes No No Yes Yes Yes No |
Bộ thứ nhất chỉ có một nút giao nên không có lượt chạy nào. Bộ thứ hai là tam giác cạnh : mọi khoảng cách đều bằng . Bộ thứ ba là đường : giải có tập độ khó . |
Bình luận