P2941 [USACO09FEB] Surround the Islands S

Farmer John 在加勒比海购置了一片地产，准备在由一系列岛屿组成的农场上养奶牛。 出于他的意愿，他要把所有的岛屿都用篱笆围上。 每个岛都是多边形的。每一次，FJ 会给多边形的一个边（即相邻的两个顶点之间）装上篱笆。对于整个岛屿，他会按照顺时针顺序装上篱笆。由于他想要给所有的岛屿都装上篱笆，某些时候，他必须从一个岛屿坐船到另一个岛屿去。 FJ 可以从任何一个顶点开始装篱笆，也可以从任何一个顶点坐船到另一个岛的某个顶点上，从这个顶点开始把该岛屿的篱笆全都装好，然后**马上**坐船原路返回。保证任意两个顶点间都有航线。在任意两个顶点之间坐船的费用会在一个矩阵中给出。 所有的岛屿由给定的 $N$ 对顶点 $V_1$，$V_2$ 描述（即：给定顶点 $V_1$ 与 $V_2$ 相邻）。每个顶点具体属于哪个岛屿**不会**在输入中给出。所有顶点由 $1$ 到 $N$ 标号。 在顶点间坐船旅行的费用由一个 $N \times N$ 的矩阵给出。保证两个岛屿间两个方向的旅行费用相等且不会超过 $1000$。 请求出 FJ 把篱笆装完所需要的最小花费。 第 $2$ 至第 $N+1$ 行：每行包含两个整数 $V_1$ 和 $V_2$，表示这两个顶点在同一个岛屿上且相邻。 第 $N+2$ 行至第 $2N+1$ 行：每行包含 $N$ 个整数，第 $i-N-1$ 行的第 $j$ 个整数表示从 $i$ 号顶点坐船到第 $j$ 号顶点的花费。

无

无

对于所有数据，保证： + $3 \leq n \leq 500$ + $1 \leq V_1,V_2 \leq N$ + 任意两个顶点之间的旅行花费 $\leq 1000$