Building Bridges

Many thanks to Clive Fraser for creating this puzzle!

In the land of Erehwon there is a large lake with many small islands. Some of the islands are connected by wooden footbridges. There are also footbridges between some of the islands and the shore. The inhabitants of Erehwon like to take a stroll around the islands by making use of the many bridges. It is also possible to walk from one shore of the lake to the other by using the bridges between the islands.

During one night a fierce storm created huge waves over the lake. A number of bridges were swept away. The next day the inhabitants were dismayed to find that they could no longer enjoy their walks among the islands. The cost of replacing all of the lost bridges was significantly greater than the amount that could be raised. After some discussion it was decided that a number of new bridges would be put in place so that it would once more be possible to walk from one lake shore to the other. The new bridges could either be replacements for bridges which had been swept away or bridges between islands which had not previously had a connecting bridge. However, it was agreed that the total cost should be the smallest cost consistent with having a walking route from one lake shore to the other.

There are N-2 islands in the lake. These are numbered from 2 to N-1. For convenience, the two opposite lake shores are numbered 1 and N. The nearest island to shore 1 is island 2 and the nearest island to shore N is island N-1. Islands with consecutive numbers are neighbouring islands. Bridges can be constructed between any pair of islands or between an island and one of the two lake shores. However, the cost of constructing the bridge is dependent on its length. If a bridge is to be constructed between islands n1 and n2 then the cost is $2000 x abs(n1-n2), where abs is the absolute value. So a bridge from island 41 to island 47 will cost $2000 X (47-41) = $12000. Similarly, a bridge from shore 1 to island 5 will cost $8000.

In this problem you will be given a list of the bridges which remain in place after the storm. You are asked to find the minimum cost of building new bridges so that it is possible to walk between the opposite shores of the lake. It is not necessary to be able to reach every one of the islands. The actual problem will have a very large number of islands and bridges. Because of the large amount of data we will use the Linear Congruential Generator to create it. This has been used before in Code Abbey problems. A random value X(n) is generated using the formula:

X(n) = (A * X(n-1) + C) % M

In this problem we will use the values A = 445, C = 700001 and M = 2097169. Note that % M means the remainder after dividing by the modulus value of M. The value X(n-1) is the previous random value to be generated by this expression. In order to generate the first random value X(1) we need to be given a value for X(0) which is called the seed for the generator. This value will be supplied as part of the data for the problem. The formula above creates a reasonable sequence of roughly random values but these are too large for direct use in the problem. For each randomly generated number X(n) we will create an island number I(n) = 1 + X(n) % N. This ensures that the island numbers lie in the range 1 to N inclusive.

Consider a small example, where the number of islands N = 20, the number of remaining bridges B = 6 and the random seed X(0) = 0 (it will not be 0 in the actual problem but will have some randomly chosen value). We need to know the islands at each end of a bridge, so for each bridge we need to generate two island numbers. The first 12 generated random numbers are: 700001, 1819434, 840897, 1603084, 1034921, 1959835, 404272, 244507, 452828, 880237, 234863, 355586. Using the calculation for I(n) above, we create the following 6 pairs of numbers.

2, 15, 18, 5, 2, 16, 13, 8, 9, 18, 4, 7

So we have bridges between islands 2 and 15, between islands 5 and 18, between islands 2 and 16 etc. Note that it is possible to have more than one bridge connecting the same pair of islands. It is also possible to have a bridge which connects an island with itself (presumably spanning an inlet on the island). The number of islands will be less than 500000 and the number of remaining bridges will be less than 8000.

One way of obtaining a walking route between the two shores in this example is to build a bridge between shore 1 and island 2 (at a cost of $2000) and a second bridge between island 16 and shore 20 (at a cost of $8000). The total cost is then $10000 and the route from shore to shore uses three bridges. Bridge 1 goes from shore 1 to island 2, bridge 2 goes from island 2 to island 16 and bridge 3 goes from island 16 to shore 20. It is not possible to create a walking route between the two shores for less than $10000.

Input/Output description: The first line of the input data will contain three space-separated integers N, B and X(0); for the number of islands, the number of remaining bridges and the random seed respectively. You need to determine the minimum cost of new bridges to create a walking route between the two lake shores. Give your answer as a single integer.

Example 1:

input:
20 6 0

answer:
10000

Example 2:

input:
406316 7179 838478

answer:
254000