===================================
Trong kì thi IOI tại Thái
Lan vừa qua, sau 2 ngày làm bài đầy căng thẳng, Tuệ cùng các thí sinh khác được
đi tham quan Thành Cổ (Ancient City), 1 địa danh du lịch khá nổi tiếng nơi
đây.Thành Cổ ngoài lối vào (được đánh số 1) và lối ra (được đánh số N), được
chia ra làm N-2 khu vực khác nhau (được đánh số từ 2 đến N-1), mỗi khu vực được
xây dựng theo 1 lối kiến trúc riêng vô cùng độc đáo. Giữa các khu vực này có
thể có các lối đi, được biểu diễn bằng ma trận A.
Hành trình của Tuệ sẽ bắt
đầu từ lối vào, tham quan các khu vực trong Thành Cổ và kết thúc ở lối ra. Là 1
người yêu thích chụp ảnh, Tuệ chắc chắn sẽ không bỏ qua 1 khu vực nào nếu cậu
ta có thể đến được nó thông qua các con đường. Tại mỗi địa điểm, nếu còn ít
nhất 1 khu vực Tuệ có thể đến được nhưng vẫn chưa đến tham quan, cậu ta sẽ chọn
khu vực gần nhất so với vị trí hiện tại của cậu ta (có thể di chuyển qua các
khu vực đã tham quan rồi hoặc lối vào, lối ra). Nếu có nhiều hơn 1 khu vực thỏa
yêu cầu, Tuệ sẽ chọn khu vực có số thứ tự nhỏ nhất.
Hãy tính tổng độ dài đường
đi trong chuyến tham quan của Tuệ. Luôn đảm bảo có ít nhất 1 cách để Tuệ di
chuyển từ lối vào đến lối ra.
Input
Dòng 1: số nguyên N
Dòng 2...N+1: dòng thứ i+1 chứa N số nguyên Ai,1 Ai,2 ... Ai,n ; trong đó Ai,j > 0 nếu có lối đi và Ai,j = 0 nếu không có ( với mọi i khác j, luôn đảm bảo Ai,j = Aj,i và Ai,i = 0 )
Dòng 2...N+1: dòng thứ i+1 chứa N số nguyên Ai,1 Ai,2 ... Ai,n ; trong đó Ai,j > 0 nếu có lối đi và Ai,j = 0 nếu không có ( với mọi i khác j, luôn đảm bảo Ai,j = Aj,i và Ai,i = 0 )
Output
Tổng độ dài chuyến tham
quan của Tuệ
Constraints
2 ≤ N ≤ 100
0 ≤ A ≤ 106
0 ≤ A ≤ 106
Example
Input:
5
0 3 2 0 0
3 0 2 4 5
2 2 0 1 0
0 4 1 0 2
0 5 0 2 0
Output:
5
0 3 2 0 0
3 0 2 4 5
2 2 0 1 0
0 4 1 0 2
0 5 0 2 0
Output:
11
Giải thích: Thứ tự các khu vực tham quan là 3, 4, 2. Hành trình cụ thể: 1 → 3 → 4 → 3 → 2 → 5.
Giải thích: Thứ tự các khu vực tham quan là 3, 4, 2. Hành trình cụ thể: 1 → 3 → 4 → 3 → 2 → 5.
==============================
Thuật giải:
- Floyd
- tham lam tìm đường đi