ACPC10I - The Cyber Traveling Salesman

In light of the exploding population on earth, a number of cities are being constructed on the moon. We would like you to assist in determining the best road system for these cities. Considering the high cost associated with building roads on the moon, all what is required is for the roads to form a cycle starting from the city that appears first in the input, passing through all other cities exactly once (but in any arbitrary order,) and then ending back to the first. (Yes, this problem is a variation of the traveling-salesman problem.)
You are given the cost of building a road between each pair of cities. Roads are one-way, but the cost for building a road from city i to j is the same as the cost of building from city j to i. When roads intersect at a location that is not a city, you must account for the cost of constructing bypassing bridges. Constructing a bypass system costs k ∗ (k − 1) ∗ C/2 where k is the number of roads intersecting at that location, and C is a given constant. Note that the cities are laid out so that no three cities fall on the same straight line.

Input

Your program will be tested on one or more test cases. Each test case is specified using 2 ∗ N + 1 lines. The first line specifies two integers: (2 < N < 9) is the number of cities and (0 < C ≤ 1, 000, 000) is the coefficient used in determining the cost of building bridges. Following the first line, the Cartesian coordinates of the cities are specified in order. Each city is specified on a separate line made of two integers: xi and yi where (−1, 000 ≤ xi , yi ≤ 1, 000). No two cities are located at the same (x, y) location.
The last N lines of a test case specify an N ∗ N matrix representing the cost of building a road between any two cities. The matrix is specified using N lines, each with N integers in a row-major format. The j th value on the ith row, denoted as cij is the cost of building a road from city-i to city-j where (0 < cij ≤ 106 ) and (cij = cji ) and (cii = 0).
The last case is followed by a line having two zeros.

Output

For each test case, print the following line:
k. M
Where k is the test case number (starting at one,) and M is minimum cost needed to build the road system.

Example

Input:
4 1
1 2
0 1
2 1
1 0
0 1 8 3
1 0 3 9
8 3 0 2
3 9 2 0
4 100
1 2
0 1
2 1
1 0
0 1 8 3
1 0 3 9
8 3 0 2
3 9 2 0
0 0

Output:
1. 10
2. 20

a


Added by:Omar ElAzazy
Date:2010-11-30
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACPC 2010

hide comments
2021-07-12 05:04:54
it only took me 24 submissions :-)

Last edit: 2021-07-13 01:05:31
2021-07-10 02:01:35
"When roads intersect at a location that is not a city, you must account for the cost of constructing bypassing bridges. Constructing a bypass system costs k ∗ (k − 1) ∗ C/2 where k is the number of roads intersecting at that location"
What is considered the same location? Are coordinates of the location of bypassing bridges integers or should they be computed and compared as real numbers / fractions ? (this is not specified in the text and it seems necessary to devise a correct solution).
2012-02-13 08:09:09 :D
It's in the description!
2011-09-20 09:10:29 ibrahim
how the bridge will be if there are more than two roads intersect
?
2011-03-31 17:41:38 :D
As for other problems, "^" is probably missing.
(0 < cij ≤ 106 ) => (0 < cij ≤ 10^6 )

Omar ElAzazy: Fixed

Last edit: 2010-12-08 01:24:23
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.