DAVIDG  Davids Greed
The King David it’s a particularly miser character. He have all the gold in his kingdom, and never lends a single coin to anyone. Years passed, and the streets in his kingdom, made by his father, King Enrique, started to deteriorate. The villagers couldn’t traffic with their carts without dropping some of their content.
This problem was affecting the merchants, because they were losing food and other stuff that they sell. So they decided to go to the castle and block the entrance, so the king couldn’t get out until he promised that he would restore the streets.
The King, tired by the annoyance of the people, decided to promess to restore the streets of his kingdom, but because he’s too greedy, he will restore only the ones that are important for the city, let’s call them “vital streets”.
The vital streets connect a commercial point A to a commercial point B in the city such that there will never exist 2 ways to go from point A to point B. This is given by some coordinates X and Y, you can assume the commercial point will be a single point in a space.
The original streets, built by King Enrique, connects every point with the other points, so point A it’s connected with point B, C, D, and so on. So restore every street would be too expensive, that’s why King David will restore only the “vital streets”, but he is not really good at this type of calculations, so he need you to write a program that help him out.
The cost of restoring a street is given by its length and some value P, that tell how much cost to restore a single unit of distance. By example, if P = 3, and the distance of points A and B it’s 3.5, then the total cost of restoring that street would be 3.5 * 3. Note: you have to round up the total cost of the street.
Input
The first line of input will consist of an integer T, denoting the number of test cases. Every test case will have by first line 2 integers, N and P, denoting the number of points and the unitary cost. Then N lines follow, every of them having 2 numbers Xi and Yi , denoting the coordinates in the cartesian plane of every commerciant points.
Output
For each test case output a single line containing this: “Scenario #i: j”, where i is the number of the test case, starting in one, and j it’s the minimum cost of restoring the streets, such as the restored streets let the villagers to go from one point to another point. Since this number can be quite large, output j mod 10^9 + 7.
Example
Input:2
4 1
35 46
29 13
44 0
27 17
3 18
18 0
11 17
2 31
Output:Scenario #1: 56
Scenario #2: 631
Constraints:
1 ≤ N ≤ 1,000
1,000 ≤ Xi , Yi ≤ 1,000
1 ≤ P ≤ 1,000
hide comments
Antonio Roberto Paoli:
20181030 01:14:33
I don't know how to solve it in this time limit, but first test case is really 56. You must round up the cost of each street before sum. Last edit: 20181101 23:56:30 

jayantisswani:
20170928 18:55:02
Is the output of the given testcases correct?


Shubham Jadhav:
20170505 11:22:56
My 100th :) 

mateifl:
20170121 12:42:24
Can be solved with Prim + priority queue in O(n^2). 

kshubham02:
20170116 12:04:31
I submitted a solution that was giving output 55 for the first test case, and expected WA.


ASHUTOSH DWIVEDI:
20160622 00:22:01
Problem Setter You should also provide no of test cases in problem.... 

ASHUTOSH DWIVEDI:
20160618 18:48:19
Last edit: 20160618 19:52:24 

ASHUTOSH DWIVEDI:
20160618 18:21:47
Last edit: 20160618 19:52:35 

shikhar0037:
20160520 21:13:28
Getting TLE on Prims also (using priority queue) . Is there any other optimisation required ? 

miloszmaki:
20160504 19:59:25
Is it possible to get AC with Kruskal on all O(n^2) edges? Did anyone manage to do that?

Added by:  Luis Arguello 
Date:  20120422 
Time limit:  0.100s0.180s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM32GCC ASM64 MAWK BC CCLANG CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Own problem. 