Problem Statement
题目简述:
给定一张无向图，每条边的边权都是 1，
所有的点用1~n编号。每个点的点权a[i]定义为这个点到1号点的最短路长度。
每个点还有一个值b[i]。
你可以通过给这张图添上若干条边来改变一些点的点权。要求最小化sigma(a[i]-b[i])^2 (1<=i<=n)。
数据范围：n<=40
There is a country with n cities, numbered 0 through n-1.
City 0 is the capital.
The road network in the country forms an undirected connected graph.
In other words:
Some pairs of cities are connected by bidirectional roads.
For every city there is at least one sequence of consecutive roads that leads from the city to the capital.
(Whenever two roads need to cross outside of a city, the crossing is done using a bridge, so there are no intersections outside of the cities.)
You are given a String[] linked that describes the road network.
For each i and j, linked[i][j] is 'Y' if the cities i and j are already connected by a direct road, and it is 'N' otherwise.
The distance between two cities is the smallest number of roads one needs to travel to get from one city to the other.
The people living outside of the capital are usually unhappy about their distance from the capital.
You are also given a int[] want with n elements.
For each i, want[i] is the desired distance between city i and the capital (city 0).
Fox Ciel is in charge of building new roads.
Each new road must again be bidirectional and connect two cities.
Once the new roads are built, the citizens will evaluate how unhappy they are with the resulting road network:
For each i: Let real[i] be the new distance between city i and the capital.
Then the people in city i increase the unhappiness of the country by (want[i] - real[i])^2.
Return the minimal total unhappiness Ciel can achieve by building some (possibly zero) new roads.