FoxAndCity
SRM 590 · 2013-06-25 · by cgy4ever
SRM 590 · 2013-06-25 · by cgy4ever · Graph Theory
Problem Statement
Problem Statement
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 aString[] 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 aint[] 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.
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
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
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.
Constraints
- n will be between 2 and 40, inclusive.
- linked will contain exactly n elements.
- Each element of linked will contain exactly n characters.
- Each character in linked will be 'Y' or 'N'.
- For each i and j, linked[i][j] = linked[j][i].
- For each i, linked[i][i] = 'N'.
- The graph described by linked will be connected.
- want will contain exactly n elements.
- Each element in want will be between 0 and n-1, inclusive.
- want[0] will be 0.
Examples
0)
{"NYN",
"YNY",
"NYN"}
{0, 1, 1}
Returns: 0
Ciel can build a road between cities 0 and 2. Then real[1]=1, real[2]=1, and the total unhappiness is 0.
1)
{"NYNN",
"YNYN",
"NYNY",
"NNYN"}
{0, 3, 3, 3}
Returns: 5
The optimal solution is not to build any new roads. Then the total unhappiness will be (3-1)^2 + (3-2)^2 + (3-3)^2 = 5.
2)
{"NYNNNY",
"YNYNNN",
"NYNYNN",
"NNYNYN",
"NNNYNY",
"YNNNYN"}
{0, 2, 2, 2, 2, 2}
Returns: 2
One of the optimal solutions is to build a road between cities 1 and 3.
3)
{"NYY","YNN","YNN"}
{0,0,0}
Returns: 2
4)
{"NYNNNN",
"YNYNNN",
"NYNYYY",
"NNYNYY",
"NNYYNY",
"NNYYYN"}
{0, 1, 2, 3, 0, 3}
Returns: 3
Submissions are judged against all 123 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FoxAndCity with a public method int minimalCost(vector<string> linked, vector<int> want) · 123 test cases · 2 s / 256 MB per case