LEM3 - Giao hàng - Trường THPT Chuyên Lê Quý Đôn

LEM3 - Giao hàng

View as PDF

Submit solution

All submissions

Best submissions

Points: 200.00 (partial)

Time limit: 1.0s

Memory limit: 1G

Input: stdin

Output: stdout

Authors:

kieulqd, ldn694

Problem type

Allowed languages

C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Sau 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_{i j} (0 < c_{i j} < 10001$ và $c_{i j}$ có thế khác $c_{j i}$ ) 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_{i j}$ $(j = 1 \dots 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

Copy

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

Copy

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

Please read the guidelines before commenting.

0

lonelywolf commented 1:21:01 pm, 09/05/2023

AC hơi xàm... mà thôi kệ =))