Ai cho em xin ý tưởng bài này với ạ (Dev C++)

BÀI 3. CHIẾN TRANH (CHIENTRANH.) Có L quốc gia đi chinh phạt các vùng đất mới. Cụ thể, có N thành phố được kết nối với nhau bằng những con đường hai chiều. Tại thời điểm 0, quốc gia i đang chiếm đóng thành phố cᵢ và các quốc gia bắt đầu đi chinh phạt các vùng đất mới theo quy tắc sau: Nếu một quốc gia chiếm đóng được một thành phố, họ sẽ cử các chiến binh di chuyển đến các thành phố khác có đường đi với thành phố vừa chiếm đóng, tất cả đều di chuyển cùng tốc độ. Nếu các chiến binh của hai quốc gia khác nhau gặp nhau trên một con đường, họ sẽ chiến đấu với nhau mãi mãi trên con đường đó. Nếu các chiến binh của hai quốc gia khác nhau tới một thành phố cùng một lúc, họ sẽ chiến đấu với nhau mãi mãi trên thành phố đó. Nếu các chiến binh của một quốc gia đến thành phố đang có chiến tranh xảy ra thì họ cũng tham gia vào cuộc chiến. Nếu các chiến binh đến một thành phố chưa có quốc gia nào khác chiếm đóng thì họ sẽ chiếm đóng thành phố này và tiếp tục cử các chiến binh di chuyển đến các thành phố khác như quy tắc 1. Chú ý: Với các quy tắc trên thì chỉ có duy nhất một quốc gia chiếm được một thành phố. Nếu chiến binh của hai quốc gia cùng đến một thành phố thì họ sẽ chiến đấu mãi mãi ở thành phố đó mà không di chuyển đến các thành phố khác. Yêu cầu: Hãy xác định các cặp quốc gia chiến đấu với nhau. Lưu ý: Các quốc gia đánh số từ 0 tới L − 1. Các thành phố được đánh số từ 0 tới N − 1. Dữ liệu Vào từ file văn bản CHIENTRANH.INP Dòng đầu tiên chứa N, L, M L dòng tiếp theo, dòng thứ i chứa cᵢ là thành phố mà quốc gia i chiếm đóng ban đầu. M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w mô tả một con đường giữa hai thành phố u và v có thời gian di chuyển là w Dữ liệu đảm bảo: Không có đường đi nối một thành phố với chính nó. Không có nhiều hơn một đường đi nối hai thành phố. Kết quả Ghi ra file văn bản CHIENTRANH.OUT Ghi ra nhiều dòng, mỗi dòng là hai số a, b mô tả quốc gia a sẽ chiến đấu với quốc gia b Các cặp được liệt kê theo thứ tự từ điển. Ví dụ CHIENTRANH.INP 8 4 8 0 2 4 6 0 1 100 1 2 100 2 3 100 3 4 100 4 5 100 5 6 100 6 7 100 7 0 1000 CHIENTRANH.OUT 0 1 0 3 1 2 2 3 Ràng buộc 20% số điểm có đồ thị là một đường thẳng: (0,1), (1,2), …, (N−2, N−1) 20% số điểm có w = 1 20% số điểm không có chiến tranh tại các thành phố 20% số điểm có 1 ≤ N, M ≤ 2000 20% số điểm còn lại không có ràng buộc gì thêm***