P16670 [CSPro 30] 电力网络

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。

西西艾弗岛电力公司需要修建一套电网对岛上的众多城镇进行供电。电网设施包括建造在城镇中的变电站，与建造在城镇间的输电线路。根据前期的考察结果，电力公司已经确定了哪些城镇之间需要建造输电线路，以使得所有城镇能够被连接成一个电力网络。每座城镇只需要建造一个变电站，却都向电力公司提供了多个建造候选地址。对于每个城镇，不同候选地址的变电站造价不同；对于城镇间的输电线路，其造价也会随着两端变电站的候选地址的变化而变化。因此，电力公司想要知道，在所有候选地址的组合中，电网的总造价（变电站造价加上输电线路造价）最低是多少。

从标准输入读入数据。 输入的第一行包括三个正整数 $N$、$M$、$K$。表示一共有 $N$ 座城镇，需要建造 $M$ 条输电线路，每座城镇都提供了 $K$ 个变电站候选地址。 接下来输入 $N$ 行，每行表示一个城镇。每行包含 $K$ 个整数，表示该城镇不同候选地址的变电站造价。 接下来 $M$ 行，每行表示一条输电线路，包含 $K^2 + 2$ 个整数。前两个整数表示该输电线路两端的城镇，范围是 $[0, N)$。第三个整数开始是大小为 $K \times K$ 的矩阵 $T$ 的行主序存储形式。$T_{ij}$ 表示当输电线路的第一个端点选择候选地址 $i$，第二个端点选择候选地址 $j$ 时的线路造价。

输出到标准输出。 输出包含一行，这一行有一个整数，表示电网的最低总造价。

### 样例解释 城镇 $0$ 与城镇 $1$ 均选择了 $0$ 号地址建造变电站。 ### 子任务 对于全部数据，保证由城镇与输电线路构成的图是无向无重边无自环的连通图，保证单个变电站与单条线路的造价均不超过 $1000$。 - 对于 $20\%$ 的数据，保证 $N \le 6, K \le 10$。 - 对于另外 $20\%$ 的数据，保证 $N \le 10^4, K \le 10, M = N - 1$。 - 对于另外 $20\%$ 的数据，保证 $N \le 10^4, K \le 10, M = N$。 - 对于另外 $20\%$ 的数据，保证 $N \le 10^4, K \le 10$。图中存在两个节点 $S、D$，保证全图去除 $D$ 节点和与 $D$ 节点相连的边后，可以构成以 $S$ 节点为根的一棵树，而且所有与 $D$ 相连的节点都属于这棵树的叶子节点。 - 对于最后 $20\%$ 的数据，保证 $N \le 10^4, K \le 10$，且度数大于 $2$ 的节点数量 $\le 6$。