1277번 - 발전소 설치 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB127238225927.350%

문제

엄청난 벼락을 맞아 많은 전선들이 끊어져 현재 전력 공급이 중단된 상태이다. 가장 심각한 문제는 1번 발전소에서 N번 발전소로 가는 중간의 전선이 끊어진 것이기에 일단 이 두 발전소를 다시 연결하는게 현재 해결해야할 첫 번째 과제이다.

발전소는 1번부터 N번까지 번호로 매겨져 2차원 격자 좌표 위에 있다. 그리고 몇몇 전선은 보존된 채 몇몇 발전소를 잇고 있다. 문제는 현재 전선과 발전소의 위치가 주어졌을 때 최소의 전선 길이를 추가로 사용하여 1번 발전소와 N번 발전소를 연결짓는 것이다. 물론 연결 짓는 중간에 다른 발전소를 거쳐갈 수 있다. 단, 안정성 문제로 어떠한 두 발전소 사이의 전선의 길이가 M을 초과할 수는 없다. 아래에 이에 대한 예를 그려놓았다.

         연결 전                          연결 후

3  . . . 7 9 . . . . .          3  . . . 7 9 . . . . .
                                          /
2  . . 5 6 . . . . . .          2  . . 5 6 . . . . . .
                                        /
1  2-3-4 . 8 . . . . .          1  2-3-4 . 8 . . . . .
   |                               |
0  1 . . . . . . . . .          0  1 . . . . . . . . .

   0 1 2 3 4 5 6 7 8 9             0 1 2 3 4 5 6 7 8 9

입력

첫 줄에는 발전소의 수 N(1 ≤ N ≤ 1,000)과 현재 남아있는 전선의 수 W(1≤ W ≤ 10,000)가 주어진다. 두 번째 줄에는 제한 길이 M(0.0 < M < 200,000.0)가 주어진다. 다음 N개의 줄에는 1번 발전소부터 N번 발전소까지 각각의 발전소의 X좌표와 Y좌표(-100,000 ≤ xi,yi  ≤ 100,000)가 차례대로 주어진다. 다음 W개의 줄에 대해 각 줄에는 두 개의 정수가 입력되어지는데 이는 현재 남아있는 전선이 잇고 있는 두 발전소를 의미한다.

출력

첫 줄에 1번 발전소와 N번 발전소를 잇는데 필요한 추가 전선 길이의 최솟값을 1000배하여 출력한다. (단, 1000배하고 난 후 나머지 소수는 반올림이 아닌 버림을 한다)

예제 입력 1 

9 3
2.0
0 0
0 1
1 1
2 1
2 2
3 2
3 3
4 1
4 3
1 2
2 3
3 4

예제 출력 1 

2828
W3sicHJvYmxlbV9pZCI6IjEyNzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMWNcdWM4MDRcdWMxOGMgXHVjMTI0XHVjZTU4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YzRcdWNjYWRcdWIwOWMgXHViY2JjXHViNzdkXHVjNzQ0IFx1YjlkZVx1YzU0NCBcdWI5Y2VcdWM3NDAgXHVjODA0XHVjMTIwXHViNGU0XHVjNzc0IFx1YjA0YVx1YzViNFx1YzgzOCBcdWQ2MDRcdWM3YWMgXHVjODA0XHViODI1IFx1YWNmNVx1YWUwOVx1Yzc3NCBcdWM5MTFcdWIyZThcdWI0MWMgXHVjMGMxXHVkMGRjXHVjNzc0XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjMmVjXHVhYzAxXHVkNTVjIFx1YmIzOFx1YzgxY1x1YjI5NCAxXHViYzg4IFx1YmMxY1x1YzgwNFx1YzE4Y1x1YzVkMFx1YzExYyBOXHViYzg4IFx1YmMxY1x1YzgwNFx1YzE4Y1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjOTExXHVhYzA0XHVjNzU4IFx1YzgwNFx1YzEyMFx1Yzc3NCBcdWIwNGFcdWM1YjRcdWM5YzQgXHVhYzgzXHVjNzc0XHVhZTMwXHVjNWQwIFx1Yzc3Y1x1YjJlOCBcdWM3NzQgXHViNDUwIFx1YmMxY1x1YzgwNFx1YzE4Y1x1Yjk3YyBcdWIyZTRcdWMyZGMgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0XHVhYzhjIFx1ZDYwNFx1YzdhYyBcdWQ1NzRcdWFjYjBcdWQ1NzRcdWM1N2NcdWQ1NjAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWFjZmNcdWM4MWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMxY1x1YzgwNFx1YzE4Y1x1YjI5NCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHViODVjIFx1YjllNFx1YWNhOFx1YzgzOCAyXHVjYzI4XHVjNmQwIFx1YWNhOVx1Yzc5MCBcdWM4OGNcdWQ0NWMgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YmE4N1x1YmE4NyBcdWM4MDRcdWMxMjBcdWM3NDAgXHViY2Y0XHVjODc0XHViNDFjIFx1Y2M0NCBcdWJhODdcdWJhODcgXHViYzFjXHVjODA0XHVjMThjXHViOTdjIFx1Yzc4N1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YmIzOFx1YzgxY1x1YjI5NCBcdWQ2MDRcdWM3YWMgXHVjODA0XHVjMTIwXHVhY2ZjIFx1YmMxY1x1YzgwNFx1YzE4Y1x1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWNkNWNcdWMxOGNcdWM3NTggXHVjODA0XHVjMTIwIFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOTRcdWFjMDBcdWI4NWMgXHVjMGFjXHVjNmE5XHVkNTU4XHVjNWVjIDFcdWJjODggXHViYzFjXHVjODA0XHVjMThjXHVjNjQwIE5cdWJjODggXHViYzFjXHVjODA0XHVjMThjXHViOTdjIFx1YzVmMFx1YWNiMFx1YzlkM1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWM1ZjBcdWFjYjAgXHVjOWQzXHViMjk0IFx1YzkxMVx1YWMwNFx1YzVkMCBcdWIyZTRcdWI5NzggXHViYzFjXHVjODA0XHVjMThjXHViOTdjIFx1YWM3MFx1Y2NkMFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIyZTgsIFx1YzU0OFx1YzgxNVx1YzEzMSBcdWJiMzhcdWM4MWNcdWI4NWMgXHVjNWI0XHViNWEwXHVkNTVjIFx1YjQ1MCBcdWJjMWNcdWM4MDRcdWMxOGMgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YzgwNFx1YzEyMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgTVx1Yzc0NCBcdWNkMDhcdWFjZmNcdWQ1NjAgXHVjMjE4XHViMjk0IFx1YzVjNlx1YjJlNC4gXHVjNTQ0XHViNzk4XHVjNWQwIFx1Yzc3NFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjNjA4XHViOTdjIFx1YWRmOFx1YjgyNFx1YjE5M1x1YzU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgXHVjNWYwXHVhY2IwIFx1YzgwNCAgICAgICAgICAgICAgICAgICAgICAgICAgXHVjNWYwXHVhY2IwIFx1ZDZjNFxyXG5cclxuMyAgLiAuIC4gNyA5IC4gLiAuIC4gLiAgICAgICAgICAzICAuIC4gLiA3IDkgLiAuIC4gLiAuXHJcbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFwvXHJcbjIgIC4gLiA1IDYgLiAuIC4gLiAuIC4gICAgICAgICAgMiAgLiAuIDUgNiAuIC4gLiAuIC4gLlxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgXC9cclxuMSAgMi0zLTQgLiA4IC4gLiAuIC4gLiAgICAgICAgICAxICAyLTMtNCAuIDggLiAuIC4gLiAuXHJcbiAgIHwgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgfFxyXG4wICAxIC4gLiAuIC4gLiAuIC4gLiAuICAgICAgICAgIDAgIDEgLiAuIC4gLiAuIC4gLiAuIC5cclxuXHJcbiAgIDAgMSAyIDMgNCA1IDYgNyA4IDkgICAgICAgICAgICAgMCAxIDIgMyA0IDUgNiA3IDggOVxyXG48XC9wcmU+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMWNcdWM4MDRcdWMxOGNcdWM3NTggXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAxLDAwMClcdWFjZmMgXHVkNjA0XHVjN2FjIFx1YjBhOFx1YzU0NFx1Yzc4OFx1YjI5NCBcdWM4MDRcdWMxMjBcdWM3NTggXHVjMjE4IFcoMSZsZTsgVyAmbGU7IDEwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MWNcdWQ1NWMgXHVhZTM4XHVjNzc0IE0oMC4wICZsdDsgTSAmbHQ7IDIwMCwwMDAuMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgMVx1YmM4OCBcdWJjMWNcdWM4MDRcdWMxOGNcdWJkODBcdWQxMzAgTlx1YmM4OCBcdWJjMWNcdWM4MDRcdWMxOGNcdWFlNGNcdWM5YzAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmMxY1x1YzgwNFx1YzE4Y1x1Yzc1OCBYXHVjODhjXHVkNDVjXHVjNjQwIFlcdWM4OGNcdWQ0NWMoLTEwMCwwMDAgJmxlOyB4aSx5aSZuYnNwOyAmbGU7IDEwMCwwMDApXHVhYzAwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBXXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MThcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAgXHVjNzc0XHViMjk0IFx1ZDYwNFx1YzdhYyBcdWIwYThcdWM1NDRcdWM3ODhcdWIyOTQgXHVjODA0XHVjMTIwXHVjNzc0IFx1Yzc4N1x1YWNlMCBcdWM3ODhcdWIyOTQgXHViNDUwIFx1YmMxY1x1YzgwNFx1YzE4Y1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCAxXHViYzg4IFx1YmMxY1x1YzgwNFx1YzE4Y1x1YzY0MCBOXHViYzg4IFx1YmMxY1x1YzgwNFx1YzE4Y1x1Yjk3YyBcdWM3ODdcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q5NFx1YWMwMCBcdWM4MDRcdWMxMjAgXHVhZTM4XHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCAxMDAwXHViYzMwXHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFx1YjJlOCwgMTAwMFx1YmMzMFx1ZDU1OFx1YWNlMCBcdWIwOWMgXHVkNmM0IFx1YjA5OFx1YmEzOFx1YzljMCBcdWMxOGNcdWMyMThcdWIyOTQgXHViYzE4XHVjNjJjXHViOWJjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWJjODRcdWI5YmNcdWM3NDQgXHVkNTVjXHViMmU0KTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEyNzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQb3dlciBGYWlsdXJlIiwiZGVzY3JpcHRpb24iOiI8cD5BIHZpY2lvdXMgdGh1bmRlcnN0b3JtIGhhcyBkZXN0cm95ZWQgc29tZSBvZiB0aGUgd2lyZXMgb2YgdGhlIGZhcm0mIzM5O3MgZWxlY3RyaWNhbCBwb3dlciBncmlkISBGYXJtZXIgSm9obiBoYXMgYSBtYXAgb2YgYWxsIE4gKDIgJmx0Oz0gTiAmbHQ7PSAxLDAwMCkgb2YgdGhlIHBvd2VycG9sZXMsIHdoaWNoIGFyZSBjb252ZW5pZW50bHkgbnVtYmVyZWQgMS4uTiBhbmQgbG9jYXRlZCBvbiBpbnRlZ2VyIHBsYW5lIGNvb3JkaW5hdGVzIHhfaSx5X2kgKC0xMDAsMDAwICZsdDs9IHhfaSAmbHQ7PSAxMDAwMDA7IC0xMDAsMDAwICZsdDs9IHlfaSAmbHQ7PSAxMDAsMDAwKS48XC9wPlxyXG5cclxuPHA+U29tZSBXICgxICZsdDs9IFcgJmx0Oz0gMTAsMDAwKSBwb3dlciB3aXJlcyBjb25uZWN0IHBhaXJzIG9mIHBvd2VyIHBvbGVzIFBpIGFuZCBQaiAoMSAmbHQ7PSBQaSAmbHQ7PSBOOyAxICZsdDs9IFBqICZsdDs9IE4pLjxcL3A+XHJcblxyXG48cD5IZSBuZWVkcyB0byBnZXQgcG93ZXIgZnJvbSBwb2xlIDEgdG8gcG9sZSBOICh3aGljaCBtZWFucyB0aGF0IHNvbWUgc2VyaWVzIG9mIHdpcmVzIGNhbiB0cmF2ZXJzZSBmcm9tIHBvbGUgMSB0byBwb2xlIE4sIHByb2JhYmx5IHRocm91Z2ggc29tZSBpbnRlcm1lZGlhdGUgc2V0IG9mIHBvbGVzKS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGxvY2F0aW9ucyBvZiB0aGUgTiBwb2xlcyBhbmQgdGhlIGxpc3Qgb2YgcmVtYWluaW5nIHBvd2VyIHdpcmVzLCBkZXRlcm1pbmUgdGhlIG1pbmltdW0gbGVuZ3RoIG9mIHBvd2VyIHdpcmUgcmVxdWlyZWQgdG8gcmVzdG9yZSB0aGUgZWxlY3RyaWNhbCBjb25uZWN0aW9uIHNvIHRoYXQgZWxlY3RyaWNpdHkgY2FuIGZsb3cgZnJvbSBwb2xlIDEgdG8gcG9sZSBOLiAmbmJzcDtObyB3aXJlIGNhbiBiZSBsb25nZXIgdGhhbiBzb21lIHJlYWwgbnVtYmVyIE0gKDAuMCAmbHQ7IE0gJmx0Oz0gMjAwLDAwMC4wKS48XC9wPlxyXG5cclxuPHA+QXMgYW4gZXhhbXBsZSwgYmVsb3cgb24gdGhlIGxlZnQgaXMgYSBtYXAgb2YgdGhlIDkgcG9sZXMgYW5kIDMgd2lyZXMgYWZ0ZXIgdGhlIHN0b3JtLiBGb3IgdGhpcyB0YXNrLCBNID0gMi4wLiBUaGUgYmVzdCBzZXQgb2Ygd2lyZXMgdG8gYWRkIHdvdWxkIGNvbm5lY3QgcG9sZXMgNCBhbmQgNiBhbmQgYWxzbyBwb2xlcyA2IGFuZCA5LjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICBBZnRlciB0aGUgc3Rvcm0gICAgICAgICAgICAgIE9wdGltYWxseSByZWNvbm5lY3RlZFxyXG5cclxuMyAgLiAuIC4gNyA5IC4gLiAuIC4gLiAgICAgICAgICAzICAuIC4gLiA3IDkgLiAuIC4gLiAuXHJcbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFwvXHJcbjIgIC4gLiA1IDYgLiAuIC4gLiAuIC4gICAgICAgICAgMiAgLiAuIDUgNiAuIC4gLiAuIC4gLlxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgXC9cclxuMSAgMi0zLTQgLiA4IC4gLiAuIC4gLiAgICAgICAgICAxICAyLTMtNCAuIDggLiAuIC4gLiAuXHJcbiAgIHwgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgfFxyXG4wICAxIC4gLiAuIC4gLiAuIC4gLiAuICAgICAgICAgIDAgIDEgLiAuIC4gLiAuIC4gLiAuIC5cclxuXHJcbiAgIDAgMSAyIDMgNCA1IDYgNyA4IDkgICAgICAgICAgICAgMCAxIDIgMyA0IDUgNiA3IDggOVxyXG48XC9wcmU+XHJcblxyXG48cD5UaGUgdG90YWwgbGVuZ3RoIGlzIHRoZW4gMS40MTQyMTM1NjIgKyAxLjQxNDIxMzU2MiA9IDIuODI4NDI3MTI0IC48XC9wPlxyXG5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiBhbmQgVzxcL3A+XHJcblxyXG48cD4qIExpbmUgMjogQSBzaW5nbGUgcmVhbCBudW1iZXI6IE08XC9wPlxyXG5cclxuPHA+KiBMaW5lcyAzLi5OKzI6IEVhY2ggbGluZSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiB4X2kgYW5kIHlfaTxcL3A+XHJcblxyXG48cD4qIExpbmVzIE4rMy4uTisyK1c6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IFBpIGFuZCBQajxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyIG9uIGEgc2luZ2xlIGxpbmUuICZuYnNwO0lmIHJlc3RvcmluZyBjb25uZWN0aW9uIGlzIGltcG9zc2libGUsIG91dHB1dCAtMS4gT3RoZXJ3aXNlLCBvdXRwdXQgYSBzaW5nbGUgaW50ZWdlciB0aGF0IGlzIDEwMDAgdGltZXMgdGhlIHRvdGFsIG1pbmltdW0gY29zdCB0byByZXN0b3JlIGVsZWN0cmljaXR5LiBEbyBub3QgcGVyZm9ybSBhbnkgcm91bmRpbmc7IHRydW5jYXRlIHRoZSByZXN1bHRpbmcgcHJvZHVjdC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO October 2008 Contest > Gold 6번

  • 문제를 번역한 사람: author6

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)