Cổng Dịch Chuyển

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một mạng lưới gồm $N$ đỉnh và $2 N$ cổng dịch chuyển (portal). Mỗi cổng nối hai đỉnh khác nhau, và mỗi cổng xuất hiện trong danh sách kề của đúng hai đỉnh.

Mỗi đỉnh $v$ có đúng 4 cổng kề: $p_{v, 1}, p_{v, 2}, p_{v, 3}, p_{v, 4}$ . Các cổng được ghép cặp: $(p_{v, 1}, p_{v, 2})$ và $(p_{v, 3}, p_{v, 4})$ . Người chơi có thể:

Di chuyển qua một cổng từ đỉnh này sang đỉnh kia
Chuyển đổi giữa hai cổng cùng cặp tại một đỉnh

Tại mỗi đỉnh $v$ , bạn có thể hoán đổi cách ghép cặp (thay vì ghép $(p_{v, 1}, p_{v, 2})$ và $(p_{v, 3}, p_{v, 4})$ , ghép $(p_{v, 1}, p_{v, 3})$ và $(p_{v, 2}, p_{v, 4})$ ) với chi phí $c_{v}$ .

Hãy tìm chi phí nhỏ nhất để tất cả $4 N$ vị trí (cổng tại đỉnh) đều liên thông với nhau.

Dữ liệu vào

Dòng 1: Số nguyên $N$
$N$ dòng tiếp theo: Mỗi dòng gồm 5 số nguyên $c_{v}, p_{v, 1}, p_{v, 2}, p_{v, 3}, p_{v, 4}$

Dữ liệu ra

Một số nguyên duy nhất: chi phí nhỏ nhất.

Ràng buộc

$2 \leq N \leq 10^{5}$
$1 \leq c_{v} \leq 1000$
Các nhãn cổng từ $1$ đến $2 N$
Mỗi nhãn cổng xuất hiện đúng hai lần

Ví dụ

Input	Output	Giải thích
5 10 1 4 8 9 11 1 2 5 6 12 9 10 2 3 3 4 3 6 7 15 10 8 7 5	13	Hoán đổi tại đỉnh 1 (chi phí 10) và đỉnh 4 (chi phí 3), tổng chi phí 13.

Bình luận

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