LEM3 - Giao hàng
View as PDFSau khi đi hội chợ trái cây cùng bạn xong Hoàng lại nhận ra đã đến giờ Hoàng phải đi làm thêm và Hoàng hiện tại đang làm nhân viên đi giao hàng. Nhiệm vụ của Hoàng là phải đi giao hàng cho hết ~n~ khách hàng với ~n~ địa chỉ được đánh số từ ~1~ đến ~n~. Đường đi từ địa chỉ khách hàng ~i~ đến địa chỉ khách hàng ~j~ là số nguyên ~c_{ij} (0 < c_{ij} < 10001~ và ~c_{ij}~ có thế khác ~c_{ji}~) có đơn vị là km. Vì người chủ của Hoàng khi giao nhiệm vụ cho anh ta thì nói rằng nếu Hoàng xong việc thì có thể về sớm nên Hoàng sẽ cố gắng làm xong sớm nhất có thể. Hãy tính xem Hoàng thời gian Hoàng giao hàng ít nhất là bao lâu nhé! Biết rằng Hoàng luôn đi đều với tốc độ ~1~ km/phút.
Yêu cầu: Hãy xác định thời gian giao hàng ít nhất của Hoàng.
Dữ liệu vào:
- Dòng ~1~ ghi số nguyên dương ~n~
- Dòng thứ ~i~ trong ~n~ dòng sau gồm ~n~ số nguyên ~c_{ij}~ ~(j=1…n)~
Output:
- Ghi ra ~1~ số nguyên duy nhất là thời gian Hoàng giao hàng (đơn vị phút).
Example:
INPUT
6
0 1 2 1 3 4
5 0 3 2 3 4
4 1 0 2 1 2
4 2 5 0 4 3
2 5 3 5 0 2
5 4 3 3 1 0
OUTPUT
8
- Subtask 1: 50% số test ứng với ~5 \leq n \leq 10~.
- Subtask 2: 50% số test còn lại ứng với ~11 \leq n \leq 15~.
Comments
AC hơi xàm... mà thôi kệ =))