2017 ACM-ICPC Xi'An Regionals problem E

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

I am keenly interested knowing the solution for a problem that our team didn't found a solution even when we are reviewing the questions, would like to hear from others thoughts on this question. :)

Problem E — Naomi with the graph

Time limit: 1~3s, I forgot the exact time limit. Memory Limit: 512 MB

As we know, Naomi is poor at math. But she practices math problems every day. The following problem is one which she met.

Naomi has a non-directed connected graph with n nodes, labeled from 1 to n, and m edges. The length of each edge is exactly 1. Each node in the graph has a special value and the value of the i-th node is denoted by A[i]. She defines dist[i] as the length of the shortest path bewteen the i-th node and the first node and especially dist[1] = 0.

Then she defines the cost of the graph as Sum( (A[i] — dist[i])^2 | for all 1 <= i <= n ).

Naomi wants to MINIMIZE the cost of the graphby inserting some new edges (the lengths of which should be 1 as well) into the graph. She could insert nothing or insert any number of new edges in her mind.

Can you help her?

Input

The input contains several test cases which is no more than 10.

In each test case, the first line contains two integers n and m ( 1 <= n <= 40, 0 <= m <= 1600).

Each of the following m lines contains two integers x and y ( 1 <= x, y <= n ) indicating an edge between the x-th node and the y-th node.

The last line of the test case contains n integers describing the array A and each element A[i] satisfies 0 <= A{i] <= 1000.

Output

For each test case, print the minimum cost of the graph in a single line.

Sample input

4 3

1 2

2 3

3 4

0 3 3 3

Sample Output

So far the best algorithm our team have came up with is a min-cut algorithm with nodes (a[i], dist[i]), but we are worried that having O(V^2) nodes will result in O(V^6) runtime per test case thus a brutal TLE.

I am grateful if someone could shed some light on this problem, I wonder if we are on a completely wrong path — It seems to be impossible to solve the problem with flow related algorithms without constructing O(V^2) nodes.