TTRIP - Tham quan Thành Cổ
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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 A
i,1
A
i,2
... A
i,n
; trong đó A
i,j
> 0 nếu có lối đi và A
i,j
= 0 nếu không có ( với mọi i khác j, luôn đảm bảo A
i,j
= A
j,i
và A
i,i
= 0 )
Output
Tổng độ dài chuyến tham quan của Tuệ
Constraints
2 ≤ N ≤ 100
0 ≤ A ≤ 10
6
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: 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.
- Người up: hphong
- Nguồn bài: Problem setter : Nguyễn Tấn Sỹ Nguyên