Hướng dẫn giải của Connecting Two Barns

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Connecting Two Barns

Hướng tiếp cận

Tìm thành phần liên thông, rồi tính chi phí kết nối thành phần chứa $1$ và thành phần chứa $N$ thông qua một thành phần trung gian.

Thuật toán

Tìm các thành phần liên thông bằng BFS/DFS.
Với mỗi thành phần $C$ , tính khoảng cách nhỏ nhất đến thành phần chứa $1$ và $N$ .
Đáp án = ${min}_{C} (srccost [C]^{2} + dstcost [C]^{2})$ .

Độ phức tạp

$O (N + M)$ mỗi bộ test.

Bình luận

Không có bình luận tại thời điểm này.