Problem
Vua Bubei II muốn đi du lịch khắp lãnh thổ của mình. Đồng thời, tuyến đường có các mong muốn sau:
1) tuyến đường nên mất ít thời gian nhất có thể (thời gian hoàng gia – là một thứ rất có giá trị và cần được bảo vệ);
2) tuyến đường phải bao gồm tất cả các khu định cư chính xác một lần (nếu nhà vua bỏ lỡ một khu định cư, thì cư dân của khu định cư đó sẽ phẫn nộ vì sự thiếu quan tâm của hoàng gia và ngừng nộp thuế; nếu nhà vua đến thăm khu định cư nhiều lần, thì cư dân của khu định cư còn lại mục định cư cũng sẽ phẫn nộ)
3) tuyến đường phải bắt đầu và kết thúc tại thủ đô của bang (sau khi đi khắp các vùng đất của mình, nhà vua phải bắt tay ngay vào công việc kinh doanh). Vốn được đưa vào lộ trình đúng 2 lần: là điểm đi và là điểm đến, không thể là giải quyết trung gian của lộ trình.
Viết chương trình sử dụng bản đồ đường đi của vương quốc để tìm một tuyến đường như vậy hoặc xác định rằng không thể đáp ứng tất cả các yêu cầu.
Đầu vào
trước tiên hãy nhập số N (tự nhiên, không vượt quá 10) – số lượng các khu định cư trong vương quốc. Sau đó, theo sau N dòng gồm N số trong mỗi – thời gian di chuyển giữa các điểm định cư (thời gian – là một số nguyên không âm, không vượt quá 500; nếu thời gian = 0, thì điều này có nghĩa là không có đường đi giữa một số điểm định cư). Khu định cư số 1 là thủ phủ của bang.
Dấu ấn
in tổng thời gian ít nhất mà Bệ hạ sẽ dành để đi đường vòng quanh lãnh thổ của mình hoặc số -1 nếu không thể xây dựng tuyến đường với các thuộc tính đã cho.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
1
0 |
0 |
| 2 |
2
0 1
10 |
2 |
| 3 |
2
0 85
85 0 |
170 |