Bài tập Lập trình về đồ thị - Bài 4: Lập lịch di chuyển cho Robot

Bài tập lập trình 4: Lập lịch di chuyển cho Robot 1. Mô tả bài toán Có hai con robot A và B di chuyển trên một đồ thị có trọng số G. Do cả hai robot đều được điều khiển bởi sóng radio nên chúng không thể ở gần nhau trong khoảng cách r. Ban đầu hai robot đứng ở đỉnh a và đỉnh b trên G. Robot tại a muốn di chuyển đến đỉnh c dọc theo một đường đi trong G, và robot tại b muốn di chuyển đến đỉnh d. Việc di chuyển này có thể mô ta dưới dạng việc lập lịch di chuyển: tại mỗi thời điểm, lịch di chuyển xác định chỉ một robot di chuyển qua một cạnh, từ một đỉnh tới một hàng xóm; cuối cùng, robot từ đỉnh a nên ở đỉnh c, và robot từ b nên ở đỉnh d. Một lịch di chuyển gọi là không gây nhiễu nếu không có thời điểm nào mà hai robot lại đứng ở hai đỉnh có khoảng cách1 ≤ r, với tham số r cho trước. Bạn hãy viết chương trình nhập vào một đồ thị có trọng số G, hai đỉnh bắt đầu a và b, hai đỉnh kết thúc c và d, và tham số r > 0. Thông báo ra màn hình một lịch di chuyển nếu có; nếu không có thông báo ’Không thể!’. Input: • Dòng đầu tiên là số đỉnh n< 100 và số cạnh m của đồ thị G. • m dòng tiếp theo mỗi dòng gồm 3 số x y w thể hiện: Đồ thị G có cạnh {x , y} với trọng số w. • dòng tiếp theo chứa bốn số a b c d là đỉnh bắt đầu và kết thúc của hai robot. • dòng cuối cùng là số r > 0. Output: Bao gồm nhiều dòng, mỗi dòng là hai số u v thể hiện các đỉnh mà hai robot đứng tại mỗi thời điểm trong lịch di chuyển. Ví dụ: Xét đồ thị dưới đây với các đỉnh bắt đầu a = 0, b = 2; các đỉnh kết thúc c = 2, d = 3; và r = 4. Ta có một lịch di chuyển được chỉ ra ở dưới đây. Khoảng cách cặp đỉnh được chỉ ra ở cột cuối để chứng minh rằng đây là một lịch di chuyển không gây nhiễu. 1 2 5 34 0 1 2 5 4 1 6 7 7 9 Lịch di chuyển khoảng cách 0 2 7 0 3 5 1 3 8 2 3 7 Nếu ta thay r trong ví dụ trên bằng 5, thì không có lịch di chuyển không nhiễu nào cả. 1khoảng cách là độ dài đường đi ngắn nhất 1 22. Một số dữ liệu Test Dữ liệu Test 1 10 12 // n m 0 4 10 0 9 11 1 4 9 2 6 5 2 8 1 3 4 11 3 6 5 4 5 2 5 7 9 7 8 3 7 9 10 8 9 4 1 3 // a b 3 4 // c d 7 // r Lịch di chuyển khoảng cách 1 3 20 1 4 9 1 0 19 4 0 10 3 0 21 3 4 11 0 1 43 6 5 7 2 8 9 10 11 9 5 1 11 5 2 9 3 10 4 Hình 1. Đồ thị của dữ liệu Test 1 3Dữ liệu Test 2 15 22 // n m 0 8 11 0 11 7 1 4 15 1 7 13 2 3 2 2 4 12 2 8 10 2 10 13 2 12 6 2 13 13 5 8 5 5 9 14 6 7 2 6 8 7 6 11 5 6 14 3 7 9 11 8 12 7 9 12 9 10 12 15 11 12 7 11 14 8 1 3 // a b 3 4 // c d 7 // r Lịch di chuyển khoảng cách 1 3 29 7 3 21 6 3 19 6 2 17 6 4 29 8 4 22 2 4 12 3 4 14 4Dữ liệu Test 3 15 23 // n m 0 2 3 0 9 6 0 10 11 1 9 5 2 4 15 2 5 14 2 7 1 2 9 5 2 11 6 2 12 14 3 6 7 3 11 7 3 12 10 3 13 14 3 14 14 4 8 2 4 12 11 5 13 15 6 11 2 8 9 8 8 12 6 8 14 11 10 12 3 1 3 // a b 3 4 // c d 7 // r Lịch di chuyển khoảng cách 1 3 23 1 12 19 9 12 14 9 4 10 2 4 15 12 4 8 3 4 18 510 3 1 4 2 13 12 8 5 9 7 6 14 0 11 11 7 15 13 2 12 10 13 6 13 5 14 2 7 5 3 11 7 9 15 7 8 Hình 2. Đồ thị của dữ liệu Test 2 62 9 1 14 8 4 12 10 5 13 3 6 11 0 7 3 6 11 5 15 14 1 5 6 14 7 7 10 14 14 2 11 15 2 8 6 11 3 Hình 3. Đồ thị của Test 3