Informatica Online Judge

  공장과 농장과 동현이 [2477 / 09AD]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 4   Total Tried : 10


The Champion of this Problem (C++) : admin - ms / 1391byte
My Best Submission (C++) : N/A

[35th 김세빈(gs17018)]
Writer ID : [gs17018]

Background

인천은 1번부터 N번까지 번호가 붙은 N개의 행성으로 이루어져 있다. 행성 간의 이동을 위해 M개의 포탈이 존재하는데, i번째 포탈은 행성 U_i와 V_i를 연결하며 포탈을 통과하는 데 C_i의 시간이 걸린다. 포탈을 통해 임의의 두 행성 사이를 이동할 수 있다.
인천에 사는 모든 사람들은 행성 1에 있는 소금 포장 "공장"에서 일하거나, 또는 행성 2에 있는 소금 "농장"(염전)에서 일한다. 1번과 2번 행성을 포함한 모든 N개의 행성에는 공장과 농장에서 일하는 사람이 모두 존재한다. 모든 사람들은 매일 아침 포탈을 이용해 자신이 사는 행성에서 자신이 일하는 행성까지 최단 경로를 따라 이동한다. 최단 경로가 여러 개 존재할 경우 아무거나 선택한다.

인천을 다스리는 동현이는 소금 장사로 막대한 돈을 벌었다. 그래서 행성 하나를 새로 구입해 그곳으로 이사하고, 포탈을 몇 개 설치하여 나머지 N개의 행성들로 이동할 수 있도록 하려고 한다. 포탈을 몇 개 설치할 것인지, 어떤 행성들과 연결할 것인지는 동현이가 마음대로 정할 수 있다. 동현이는 인천의 물리 법칙 또한 지배하므로, 각각의 포탈을 통과하는 데 걸리는 시간 또한 마음대로 정할 수 있다. 시간은 음수일 수 없지만, 반드시 정수일 필요는 없다. 새로운 포탈은 반드시 새로 구입한 행성과 연결되어야 한다.
시끄러운 것을 싫어하는 동현이는 새로운 행성에 사람이 많이 지나다니는 것을 원치 않는다. 따라서 아래 두 조건을 만족하도록 포탈을 설치하려고 한다.
<조건 1> 모든 사람들이 새로운 행성을 거치지 않고도 최단 경로를 따라 공장으로 이동할 수 있어야 한다. 즉, 모든 행성 i에 대해, 새로운 포탈을 설치한 뒤에도 행성 i에서 행성 1로 최단 경로를 따라 이동하는 데 걸리는 시간이 변하지 않아야 한다.
<조건 2> 모든 사람들이 새로운 행성을 거치지 않고도 최단 경로를 따라 농장으로 이동할 수 있어야 한다. 즉, 모든 행성 i에 대해, 새로운 포탈을 설치한 뒤에도 행성 i에서 행성 2로 최단 경로를 따라 이동하는 데 걸리는 시간이 변하지 않아야 한다.

물론, 새로운 행성에 포탈을 설치하지 않거나 새로운 포탈을 통과하는 데 시간이 많이 걸리도록 하면 위의 두 조건을 쉽게 만족시킬 수 있다. 하지만 동현이는 효율적인 통치를 위해 나머지 N개의 행성 사이를 빠르게 오갈 수 있기를 원한다. 즉, 새로운 행성에서 나머지 N개의 행성까지 최단 경로를 따라 이동하는 데 걸리는 시간의 평균을 최소화하고자 한다. 동현이를 도와주자!

문제의 조건이 "농장과 동현이" 문제와 다르다는 점에 유의하라.

Input

첫째 줄에 테스트 케이스의 갯수 T가 주어진다.
각각의 테스트 케이스는 (M + 1)개의 줄로 이루어져 있다. 첫 번째 줄에는 행성의 갯수와 포탈의 갯수를 나타내는 두 정수 N과 M이 주어진다.
다음 M개의 줄 중 (i + 1)번째 줄에는 세 정수 U_i, V_i, C_i가 주어진다. 이는 i번째 포탈이 행성 U_i와 V_i를 연결하며, 포탈을 통과하는 데 C_i의 시간이 걸린다는 것을 의미한다.

모든 테스트 케이스는 아래의 조건을 만족한다.

2 <= N <= 10^5
1 <= M <= 3 * 10^5
1 <= U_i, V_i <= N
U_i != V_i
0 <= C_i <= 10^6
주어진 그래프는 연결 그래프이다.

하나의 입력 데이터에서 주어지는 모든 테스트 케이스의 N의 합은 555,555를 넘지 않으며, M의 합은 2,222,222를 넘지 않는다.

어떤 두 행성 사이를 연결하는 포탈이 두 개 이상 존재할 수 있음에 유의하라.

Output

각각의 테스트 케이스에 대해, 새로운 행성에서 나머지 N개의 행성까지 최단 경로를 따라 이동하는 데 걸리는 시간의 평균의 최솟값을 출력한다. 정답과의 절대 또는 상대 오차가 10^-6 이내일 경우 정답으로 인정된다.

IO Example

Input Example

1
3 3
1 2 5
2 3 5
3 1 1

Output Example

1.83333333

Hint

아래와 같이 포탈을 설치하면 세 행성까지 최단 경로를 따라 이동하는 데 걸리는 시간이 각각 0.5, 0.5, 4.5가 되며 이때의 평균은 (0.5 + 0.5 + 4.5) / 3 = 1.83333333333...이다.
1. 새로운 행성과 행성 1을 포탈로 연결한 뒤 포탈을 통과하는 데 걸리는 시간을 0.5로 한다.
2. 새로운 행성과 행성 2를 포탈로 연결한 뒤 포탈을 통과하는 데 걸리는 시간을 0.5로 한다.
3. 새로운 행성과 행성 3을 포탈로 연결한 뒤 포탈을 통과하는 데 걸리는 시간을 4.5로 한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]