Đề thi cuối học kỳ môn LÝ THUYẾT ĐỒ THỊ ( Lớp 07HCA - TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN )

Một tay đua môtô đã sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhấtvượt qua sa mạc Sahara. Sau khi đã vẽ được đường đi trên bản đồ theo hệ thống các nút, anh ta tiến hành chạy theo con đường đó.
Nội dung trích xuất từ tài liệu:
Đề thi cuối học kỳ môn LÝ THUYẾT ĐỒ THỊ ( Lớp 07HCA - TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN ) TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN Đề thi cuối học kỳ môn LÝ THUYẾT ĐỒ THỊ Lớp 07HCA Thời gian : 55 phút (Được tham khảo tài liệu)Lưu ý: Lưu bài với tên project là mã số sinh viên của người thi. Đầu chương trình ghi chú: /* MSSV: . . . Họ tên: . . . Lớp: . . .Đề số: . . . */ Chỉ nộp file MSSV.cpp mà thôi.Đề 1: Một tay đua môtô đã sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhấtvượt qua sa mạc Sahara. Sau khi đã vẽ được đường đi trên bản đồ theo hệ thốngcác nút, anh ta tiến hành chạy theo con đường đó. Tuy nhiên khi đi được hơn x km(anh ta phải đến một nút xác định rồi mới kiểm tra có hơn x không), anh ta nhậnđược tin một con đường bị hư hỏng (con đường chưa qua).Với thuật toán Dijkstra, bạn hãy vẽ giúp anh ta con đường tiếp theo để đến đíchngắn nhất. Nếu không có đường đi phải thông báo là không tìm thấy.Input: Nhập từ file LoTrinh.txt  Dòng đầu chứa N là số điểm trên sa mạc, các điểm được đánh thứ tự từ 0 đến N-1.  Dòng thứ 2 là điểm bắt đầu đi và điểm đến.  Dòng thứ 3 là lộ trình đã đi khi vừa mới vượt qua x km.  Dòng thứ 4 là x km.  Dòng thứ 5 là con đường hỏng (biểu diễn bởi 2 số cách nhau khoảng trắng)  N dòng tiếp theo, mỗi dòng chứa N số (không âm) biểu diễn ma trận độ dài của các tuyên đường trên sa mạc Sahara (các số trên cùng dòng cách nhau bởi khoảng trắng).Output: a) Ghi ra file DaDi.txt chiều dài con đường mà anh ta đã đi khi vừa mới vượt qua x km. b) Ghi ra file ChieuDai.txt tổng độ dài con đường anh ta đi (nếu có). c) Ghi ra file ChiTiet.txt lộ trình con đường anh ta thực hiện (nếu có).Trong trường hợp không tìm thấy đường đi ghi vào file câu (b),(c) số 0. Hết.