HUGO (MS0023)GIA ĐÌNH HUGO BỊ NHỐT VÀO MỘT CĂN PHÒNG BÍ MẬT CỦA MỤ PHÙ...

Bài 2: Hugo (MS0023)Gia đình Hugo bị nhốt vào một căn phòng bí mật của mụ phù thủy Scyla. Một đêm nọ, nhân cơ hội mụphù thủy ngủ say, gia đình Hugo đã tìm cách thoát khỏi căn phòng đó nhưng trước mặt anh là một mêcung. Hugo đã lấy được bản đồ mê cung, mê cung này có thể mô tả thành n địa điểm (được đánh số từ 1đến n), giữa hai điểm của mê cung có thể có đường đi bộ trực tiếp hoặc phải vượt sông hoặc không thể điqua được. Việc vượt sông là rất nguy hiểm vì bản đồ có ghi chú dưới sông có thể có cá sấu. Giả thiêt rằngHugo ban đầu ở điểm 1 và điểm cần đến là n. Hãy cho biết tổng độ dài đường bộ mà Hugo phải đi ngắnnhất là bao nhiêu sao cho số lần vượt sông là ngắn nhấtDữ liệu vào: từ file HUGO.INPDòng đầu tiên ghi số nguyên dương N (N≤100)Tiếp đến là một số dòng, mỗi dòng ghi 3 số x, y, z (0≤z≤100)Nếu z=0 thì giữa điểm x và y có sôngNếu z<>0 thì cho biết độ dài đường bộ qua lại trực tiếp giữa x và y là zKết quả: Ghi vào file HUGO.OUT gồm tổng độ dài đường bộ mà Hugo phải đi và số lần Hugo phải vượtsông thỏa mãn yêu cầu (mỗi số ghi trên 1 dòng). Nếu không có đường đi ghi -1ROWN.INP ROWN.OUT HUGO.INP HUGO.OUT835 6161 2 122 3 052 4 03 4 091 3 544 6 273 6 01 5 05 6 4TRƯỜNG THPT CHUYÊN LÝ TỰ TRỌNG – CẦN THƠ