Đoàn thanh tra gồm hai thành viên và cần lần lượt đi kiểm tra công ty trong thành phố Free Contest. Để có thể sử dụng các thông tin của một số công ty trong việc kiểm tra các công ty quan trọng và việc thanh tra được tiến hành nhanh chóng, họ sẽ phân công các công ty cho nhau sao cho:
Mỗi công ty chỉ được kiểm tra bởi đúng một thanh tra.
Các thanh tra có thể kiểm tra các công ty theo thứ tự lần lượt từ công ty đến công ty .
Tổng quãng đường di chuyển của hai thanh tra là ít nhất. Lưu ý do tính chất đặc thù của ngành thanh tra, để di chuyển đến công ty sau khi vừa kiểm tra xong công ty , các thanh tra sẽ phải đi theo một đường đi đã được quy định trước. Đường đi này chưa chắc đã là
đường đi ngắn nhất giữa hai công ty và .
Cụ thể hơn, gọi các giao điểm theo thứ tự mà thanh tra là và các giao điểm theo thứ tự mà thanh tra là , ta có:
Mỗi số nguyên từ đến xuất hiện trong dãy đúng một lần.
Gọi là quãng đường di chuyển từ công ty đến công ty theo đường đi đã được quy định trước, ta có tổng nhỏ nhất có thể.
Yêu cầu: Viết chương trình giúp đoàn thanh tra tính tổng quãng đường di chuyển ngắn nhất có thể của cả hai thanh tra.
Dữ liệu vào:
Dòng đầu tiên gồm một số nguyên dương ;
dòng tiếp theo, mỗi dòng gồm một số nguyên có giá trị từ đến . Ở dòng thứ , số
nguyên thứ là quãng đường di chuyển từ công ty đến công ty theo đường đi đã được quy định trước. Dữ liệu vào đảm bảo nếu thì .
Dữ liệu ra:
Gồm một dòng duy nhất chứa một số nguyên là tổng quãng đường di chuyển ngắn nhất của cả hai thanh tra.
Ví dụ:
Dữ liệu vào:
4
0 2 3 4
2 0 1 5
3 2 0 7
8 6 5 0
Dữ liệu ra:
3
Giải thích
Thanh tra sẽ đi kiểm tra các công ty . Tổng quãng đường di chuyển của thanh tra là ;
Thanh tra sẽ đi kiểm tra công ty . Tổng quãng đường di chuyển của thanh tra là .
