P7528 [USACO21OPEN] Portals G

Bessie is in a network consisting of $N$ nodes labeled $1\dots N$ and $2N$ portals labeled $1\cdots 2N$. Each portal connects two different nodes $u$ and $v$ ($u \ne v$). There may be multiple portals connecting the same pair of nodes. Each node $v$ is connected to four distinct portals. The list of portals adjacent to $v$ is given by $p_v=[p_{v,1},p_{v,2},p_{v,3},p_{v,4}]$. Your current position can be represented by an ordered pair (current node, current portal), i.e. a pair $(v,p_{v,i})$, where $1 \le v \le N$ and $1 \le i \le 4$. You can change your position using either of the following operations: - 1. Change the current node by going through the current portal. - 2. Change the current portal. At each node, the first two portals in the list are paired, and the last two portals are also paired. That is, if your position is $(v,p_{v,2})$, you may switch to portal $(v,p_{v,1})$, and vice versa. Similarly, if your position is $(v,p_{v,3})$, you may switch to portal $(v,p_{v,4})$, and vice versa. There is no other way to change portals (for example, you **cannot** switch from portal $p_{v,2}$ to portal $p_{v,4}$). There are $4N$ distinct positions in total. Unfortunately, it is not necessarily true that every position can reach every other position through a sequence of operations. Therefore, for a cost of $c_v$ mooney, you may reorder the list of portals adjacent to $v$ in any order. After that, the first two portals in the list are paired with each other, and the last two portals are paired with each other. For example, if you reorder the portals adjacent to $v$ into $[p_{v,3},p_{v,1},p_{v,2},p_{v,4}]$, this means that when you are at node $v$, - If you are currently at portal $p_{v,1}$, you can switch to portal $p_{v,3}$, and vice versa. - If you are currently at portal $p_{v,2}$, you can switch to portal $p_{v,4}$, and vice versa. You can no longer switch from portal $p_{v,1}$ to portal $p_{v,2}$, or from $p_{v,3}$ to $p_{v,4}$, and vice versa. Compute the minimum amount of mooney needed to modify the network so that every position can reach every other position. The input guarantees that there exists at least one valid way to modify the network.

The first line contains $N$. The next $N$ lines each describe one node. Line $v+1$ contains five space-separated integers $c_v,p_{v,1},p_{v,2},p_{v,3},p_{v,4}$. The input guarantees that for each $v$, $p_{v,1},p_{v,2},p_{v,3},p_{v,4}$ are all distinct, and each portal appears in the adjacency lists of **exactly two nodes**.

Output one line containing the minimum amount of mooney needed to modify the network so that every position can reach every other position.

#### Sample Explanation It is enough to reorder the adjacency lists of nodes $1$ and $4$. This costs a total of $c_1+c_4=13$ mooney. We can make $p_1=[1,9,4,8]$ and $p_4=[7,4,6,3]$. #### Constraints $2 \le N \le 10^5$, $1 \le c_v \le 10^3$. Translated by ChatGPT 5