Câu 3 (7 điểm): Du lịch Bạc Liêu.
Tỉnh Bạc Liêu có n địa điểm du lịch và được đánh số từ 1 đến n. Biết rằng
đường đi giữa hai địa điểm bất kì (nếu có) đều là đường đi hai chiều. Sơ đồ mạng lưới
giao thông của n địa điểm này cho bởi ma trận a[i,j], trong đó:
- a[i,j] là độ dài đường đi từ địa điểm i đến địa điểm j (a[i,j] là số nguyên dương
và a[i,j] ≤ 100).
- a[i,j] = 0 nếu không có đường đi từ địa điểm i đến j.
- a[i,j] = a[j,i]
- a[i,i] = 0
Một đoàn du lịch xuất phát từ địa điểm P và muốn đến địa điểm Q, nhưng họ
không biết nên đi theo đường nào là ngắn nhất để tiết kiệm chi phí và thời gian. Bạn là
lập trình viên, hãy giúp họ giải quyết bài toán trên hoặc đưa ra thông báo không tồn tại
đường đi giữa P và Q.
Dữ liệu vào: Ghi trong tập tin văn bản DULICH.INP gồm:
- Dòng 1: Chứa số n, P, Q (n ≤ 100)
- n dòng tiếp theo, mỗi dòng ghi n số a[i,1], a[i,2], …, a[i,n]
Các số cách nhau ít nhất một khoảng trắng.
Dữ liệu ra: Ghi vào tập tin văn bản DULICH.OUT
Nếu không có đường đi thì ghi KHONG, ngược lại thì
- Dòng 1: Tổng độ dài đường đi.
- Dòng 2: Các địa điểm mà đoàn cần đi qua.
Ví dụ:
DULICH.INP DULICH.OUT
4 1 4
6
1 2 3 4
0 3 0 10
3 0 1 0
0 1 0 2
10 0 2 0
Bạn đang xem câu 3 - Đề thi Chọn học sinh giỏi lớp 12 vòng Tỉnh năm 2011 - 2012 môn Tin học Bảng A (Ngày 5/11/2011) - Sở Giáo dục Đào tạo Bạc Liêu