Trao đổi tình báo
Đề bài
Mô tả
Dù vẫn còn là học sinh trung học, Carmen và Juni đã là những điệp viên hàng đầu.
Carmen và Juni sống ở Byteland, có thể mô hình hóa bằng một đồ thị vô hướng liên thông gồm đỉnh và cạnh. Sáng nay, đúng 8 giờ, Carmen đi từ nhà ở đỉnh đến trường ở đỉnh . Cũng đúng 8 giờ, Juni đi từ nhà ở đỉnh đến trường ở đỉnh .
Trên đường đến trường hôm nay, Carmen và Juni muốn trao đổi thông tin tình báo đã thu thập được. Là những điệp viên hàng đầu, họ chỉ cần ở cùng một vị trí (tại một đỉnh hoặc tại một điểm trên một cạnh) vào cùng một thời điểm là có thể trao đổi thông tin.
Để đơn giản, giả sử Carmen và Juni ở lại trường mãi mãi sau khi đến trường. Điều này cũng có nghĩa là sau khi đến trường, họ có thể chờ ở đó và trao đổi thông tin vào một thời điểm muộn hơn.
Tuy nhiên, Carmen và Juni không có thời gian để lãng phí: mỗi người luôn đi theo một đường đi ngắn nhất từ nhà đến trường. Nếu có nhiều đường đi ngắn nhất, mỗi người có thể chọn bất kỳ đường nào trong số đó.
Carmen và Juni muốn biết có bao nhiêu vị trí khác nhau mà họ có thể trao đổi thông tin. Lưu ý rằng nếu họ có thể gặp nhau tại cùng một vị trí vào hai thời điểm khác nhau, vị trí đó chỉ được tính một lần. Nếu họ có thể gặp nhau tại hai vị trí khác nhau trên cùng một cạnh, cả hai vị trí đều được tính.
Carmen và Juni có cùng tốc độ và tốc độ của họ không thay đổi. Nếu đi hết một cạnh mất phút thì đi được phần của cạnh đó (với ) mất đúng phút.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu có dạng:
- Dòng đầu tiên chứa hai số nguyên và .
- Dòng thứ hai chứa bốn số nguyên , , , .
- dòng tiếp theo, dòng thứ chứa ba số nguyên , , : có một cạnh nối và , và cả Carmen lẫn Juni đều mất phút để đi hết cạnh này. Đồ thị được đảm bảo liên thông.
Dữ liệu vào kết thúc bằng một dòng chứa hai số ; không cần xử lý dòng này.
Dữ liệu ra
Với mỗi bộ dữ liệu, gọi là số vị trí khác nhau mà Carmen và Juni có thể trao đổi thông tin. Nếu , in ra trên một dòng. Ngược lại, in ra trên một dòng.
Ràng buộc
- .
- ; ; .
- ; ; .
- Tổng của tất cả các bộ dữ liệu không vượt quá . Tổng của tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 6 1 3 4 5 1 2 10 2 3 20 1 3 30 4 2 10 2 5 30 4 5 40 0 0 |
1 | Carmen đi từ đến có hai đường ngắn nhất độ dài ; Juni đi từ đến có hai đường ngắn nhất độ dài . Họ có thể gặp nhau tại đỉnh lúc 8 giờ 10 nếu Carmen đi và Juni đi . |
| 5 6 1 3 4 5 1 2 10 2 3 20 1 3 20 4 2 10 2 5 30 4 5 40 0 0 |
0 | Carmen chỉ có một đường ngắn nhất độ dài là , nên họ không thể gặp nhau. |
| 3 2 1 3 2 3 1 3 10 2 3 20 0 0 |
1 | Cả hai cùng học ở đỉnh . Carmen đến trường lúc 8 giờ 10, Juni đến lúc 8 giờ 20. Carmen có thể chờ ở trường đến khi Juni tới và trao đổi thông tin lúc 8 giờ 20. |
Bình luận