USACO 2021 - Open - Gold - Portals


Submit solution

Points: 0.30
Time limit: 1.0s
Memory limit: 256M

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=1138
Problem type

Bessie đang ở trong một mạng lưới bao gồm ~N~ ~(2 \le N \le 10^5)~ đỉnh được đánh số từ ~1~ tới ~N~ và ~2N~ cổng dịch chuyển được đánh số từ ~1~ đến ~2N~. Mỗi cổng dịch chuyển kết nối hai đỉnh ~u~ và ~v~ khác nhau ~(u \neq v)~. Có thể có nhiều cổng dịch chuyển kết nối một cặp đỉnh.

Từ mỗi đỉnh ~v~ Bessie có thể đi qua bốn cổng dịch chuyển khác nhau. Danh sách cổng dịch chuyển tại ~v~ được biểu diễn bằng ~p_v = [p_{v,1}, p_{v,2}, p_{v,3}, p_{v,4}]~.

Vị trí hiện tại của bạn ấy có thể được biểu diễn bằng một cặp số ~(~đỉnh hiện tại, cổng dịch chuyển hiện tại~)~, hay nói cách khác, là một cặp số ~(v, p_{v, i})~ với ~1 \le v \le N~ và ~ 1 \le i \le 4~. Bạn ấy có thể thực hiện một trong hai thao tác sau để thay đổi vị trí hiện tại:

  • Thay đổi vị trí đỉnh hiện tại bằng cách đi qua cổng dịch chuyển hiện tại.
  • Thay đổi cổng dịch chuyển hiện tại. Tại mỗi đỉnh, hai cổng dịch chuyển đầu trong danh sách liên kết với nhau, tương tự với hai cổng dịch chuyển cuối danh sách. Tức là, nếu vị trí hiện tại của Bessie là ~(v, p_{v,2})~ thì bạn ấy có thể chuyển sang ~(v, p_{v,1})~ và ngược lại. Tương tự, nếu vị trí hiện tại của Bessie là ~(v, p_{v,3})~ thì bạn ấy có thể chuyển sang ~(v, p_{v,4})~ và ngược lại. Những cách thay đổi cổng dịch chuyển còn lại là không được cho phép (Ví dụ: bạn ấy không thể chuyển từ vị trí ~(v, p_{v,2})~ sang vị trí ~(v, p_{v,4})~).

Như vậy, có tổng cộng ~4N~ vị trí khác nhau. Đáng tiếc rằng, không phải vị trí nào cũng có thể đến được từ mọi vị trí khác qua một dãy các thao tác. Vì vậy, với giá ~c_v~ ~(1 \le c_v \le N)~ đồng tiền, bạn ấy có thể thay đổi thứ tự các cổng dịch chuyển tại đỉnh ~v~. Sau đó, hai cổng dịch chuyển đầu danh sách liên kết với nhau, tương tự với hai cổng dịch chuyển cuối danh sách.

Ví dụ, nếu Bessie thay đổi danh sách cổng dịch chuyển tại đỉnh ~v~ thành ~[p_{v,3}, p_{v,1}, p_{v,2}, p_{v,4}]~, tức lầ nếu bạn ấy đang ở đỉnh ~v~, bạn ấy có thể:

  • Chuyển từ vị trí ~(v, p_{v,1})~ sang ~(v, p_{v,3})~ và ngược lại.
  • Chuyển từ vị trí ~(v, p_{v,2})~ sang ~(v, p_{v,4})~ và ngược lại.

Bạn hãy giúp Bessie tính lượng đồng tiền cần ít nhất để thay đổi mạng lưới sao cho từ một vị trí bất kì có thể tới bất kì vị trí nào khác. Dữ liệu đầu vào đảm bảo có ít nhất một cách biến đổi để thu được hệ thống thỏa mãn.

Input

Dòng đầu tiên chứa số ~N~.

~N~ dòng tiếp theo, mỗi dòng miêu tả một đỉnh. Dòng ~v + 1~ chứa năm số nguyên ~c_v,p_{v,1}, p_{v,2}, p_{v,3}, p_{v,4}~.

Dữ liệu đầu vào đảm bảo với mỗi v, ~p_{v,1}, p_{v,2}, p_{v,3}, p_{v,4}~ khác nhau đôi một, và mỗi cổng dịch chuyển xuất hiện trong đúng dãy cổng dịch chuyển của hai đỉnh.

Output

Một dòng duy nhất chứa số lượng đồng tiền tối thiểu để biến đổi hệ thống sao cho từ một vị trí bất kì có thể tới bất kì vị trí nào khác.

Sample Input

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

Sample Output

13

Giải thích

Một đáp án chính là thay đổi danh sách cổng dịch chuyển của đỉnh ~1~ và ~4~ - thay đổi ~p_1 = [1,9,4,8]~ và ~p_4 = [7,4,6,3]~. Cách này cần ~c_1 + c_4 = 13~ đồng tiền.

Ràng buộc

  • Test 1 là test ví dụ.
  • Các test 2-4, ~c_v = 1~ với mọi ~v~.
  • Các test 5-12 không có thêm ràng buộc nào.

Comments

There are no comments at the moment.