U158671 [USACO21OPEN] Portals G

题目来源：USACO 2021 Open Gold Problem 2

Bessie 位于一个由 N（$2≤N≤10^5$）个编号为 $1…N$ 的结点以及 $2N$ 个编号为 $1…2N$ 的传送门所组成的网络中。每个传送门连接两个不同的结点 $u$ 和 $v$（$u≠v$）。可能有多个传送门连接同一对结点。 每个结点 $v$ 与四个不同的传送门相连。与 $v$ 相连的传送门列表由 $p_v=[p_{v,1},p_{v,2},p_{v,3},p_{v,4}]$ 给出。 你的当前位置可以用有序对（当前结点，当前传送门）表示；即一个有序对 $(v,p_{v,i})$，其中 $1≤v≤N$ 以及 $1≤i≤4$。你可以使用以下任一操作来改变你的当前位置： 1. 由穿过当前传送门来改变当前结点。 2. 改变当前传送门。在每一个结点上，列表的前两个传送门是配对的，后两个传送门也是配对的。也就是说，如果你的当前位置是 $(v,p_{v,2})$，你可以转而使用传送门 $(v,p_{v,1})$，反之亦然。类似地，如果你的当前位置是 $(v,p_{v,3})$，你可以转而使用传送门 $(v,p_{v,4})$，反之亦然。没有其他改变传送门的方式（例如，你不能从传送门 $p_{v,2} 转去传送门 $p_{v,4}$）。 总共有 $4N$ 个不同的位置。不幸的是，并不一定每一个位置都可以从另外的每一个位置经过一系列操作而到达。所以，以 $c_v$（$1≤c_v≤1000$）哞尼的代价，你可以以任意顺序重新排列与 $v$ 相邻的传送门列表。在此之后，列表中的前两个传送门互相配对，同时后两个传送门也互相配对。 例如，如果你将与 $v$ 相邻的传送门以 $[p_{v,3},p_{v,1},p_{v,2},p_{v,4}]$ 的顺序重新排列，这意味着如果你位于结点 $v$， - 如果你当前位于传送门 $p_{v,1}$，你可以转而使用传送门 $p_{v,3}$，反之亦然。 - 如果你当前位于传送门 $p_{v,2}$，你可以转而使用传送门 $p_{v,4}$，反之亦然。 - 你不再能够从传送门 $p_{v,1}$ 转至传送门 $p_{v,2}$，或从传送门 $p_{v,3}$ 转至 $p_{v,4}$，反之亦然。 计算修改这一网络使得每一个位置都可以从另外的每一个位置到达所需要花费的哞尼的最小数量。输入保证存在至少一种修改网络的合法方式。

输入的第一行包含 $N$。 以下 $N$ 行每行描述一个结点。第 $v+1$ 行包含五个空格分隔的整数 $c_v,p_{v,1},p_{v,2},p_{v,3},p_{v,4}$ 。 输入保证对于每一个 $v$，$p_{v,1}$, $p_{v,2}$, $p_{v,3}$, $p_{v,4}$ 各不相同，且每个传送门出现在恰好两个结点的邻接表中。

输出一行，包含修改这一网络使得每一个位置都可以从另外的每一个位置到达所需要花费的哞尼的最小数量。

重新排列结点 $1$ 和 $4$ 的邻接表就已足够。这需要总计 $c_1+c_4=13$ 哞尼。我们可以使 $p_1=[1,9,4,8]$ 以及 $p_4=[7,4,6,3]$。 测试点性质： - 测试点 2-4 中，对于所有的 $v$，$c_v=1$。 - 测试点 5-12 没有额外限制。