P16670 [CSPro 30] Power Network

Luogu’s testdata is only for non-official communication and is not official testdata. Official judging link: 。

The power company on Xixi Aifu Island needs to build a power grid to supply electricity to many towns on the island. The grid facilities include substations built in towns and transmission lines built between towns. Based on earlier surveys, the company has already determined which pairs of towns need transmission lines so that all towns can be connected into one power network. Each town only needs to build one substation, but each town provides multiple candidate locations. For each town, the substation cost differs among candidate locations. For each transmission line between two towns, its cost also changes with the candidate locations chosen for the substations at its two ends. Therefore, the company wants to know: among all combinations of candidate locations, what is the minimum possible total cost of the power grid (substation costs plus transmission line costs).

Read input from standard input. The first line contains three positive integers $N$, $M$, and $K$. There are $N$ towns in total, $M$ transmission lines to be built, and each town provides $K$ candidate substation locations. Then follow $N$ lines, each describing one town. Each line contains $K$ integers, representing the substation costs for the different candidate locations of that town. Then follow $M$ lines, each describing one transmission line. Each line contains $K^2 + 2$ integers. The first two integers specify the two endpoint towns of the line, in the range $[0, N)$. Starting from the third integer is a row-major storage of a $K \times K$ matrix $T$. $T_{ij}$ denotes the line cost when the first endpoint chooses candidate location $i$ and the second endpoint chooses candidate location $j$.

Write to standard output. Output one line containing one integer, representing the minimum total cost of the power network.

### Sample Explanation Both town $0$ and town $1$ choose location $0$ to build the substation. ### Subtasks For all testdata, the graph formed by towns and transmission lines is guaranteed to be a connected undirected graph with no multiple edges and no self-loops. The cost of any single substation and any single line is at most $1000$. - For $20\%$ of the testdata, $N \le 6, K \le 10$。 - For another $20\%$ of the testdata, $N \le 10^4, K \le 10, M = N - 1$。 - For another $20\%$ of the testdata, $N \le 10^4, K \le 10, M = N$。 - For another $20\%$ of the testdata, $N \le 10^4, K \le 10$. There exist two nodes $S$ and $D$. After removing node $D$ and all edges incident to $D$, the remaining graph forms a tree rooted at node $S$, and all nodes adjacent to $D$ are leaves of this tree. - For the last $20\%$ of the testdata, $N \le 10^4, K \le 10$, and the number of nodes with degree greater than $2$ is $\le 6$。 Translated by ChatGPT 5