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

문제

2100년, 민식이는 남극에 살고 있다. 남극에는 N개의 마을이 있고, 몇 개는 좁은 일방 통행 도로로 연결되어 있다.

남극의 대통령은 남극에 경찰서를 설치하기로 결심했다. 각 마을에 경찰서를 설치하는 비용이 주어진다. 그러나, 꼭 모든 마을에 경찰서를 설치할 필요는 없다. 하나의 조건은 모든 마을은 경찰서에서 도로를 통해 갈 수 있어야 한다.

다음 대통령 선거가 다가오기 때문에, 대통령은 비싼 경찰서 설치 비용을 노출시키지 않으려고 한다. 따라서, 대통령은 조건을 만족시키면서, 경찰서를 설치하는데 드는 비용의 평균값을 최소로 하려고 한다.

이때, 경찰서를 설치하는 비용과, 도로의 정보가 주어졌을 때, 조건을 만족시키면서, 경찰서를 설치하는데 드는 비용의 평균값을 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 마을의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 마을부터 경찰서를 설치하는데 드는 비용이 주어진다. 이 값은 1000보다 작거나 같은 자연수이다. 셋째 줄부터 N개의 줄에는 도로의 정보가 주어진다. 도로의 정보는 인접행렬 형식으로 주어지고, 셋째 줄에서부터 i번째 줄의 j번째 값이 Y라면 i에서 j로 가는 도로가 있는 것이고, N이라면, i에서 j로 가는 도로가 없는 것이다. 그리고, i에서 i로 가는 도로는 없다.

출력

첫째 줄에 문제의 정답을 출력한다. 절대/상대 오차는 10-9까지 허용한다.

예제 입력 1

4
1 2 3 4
NYNN
NNYN
NNNY
YNNN

예제 출력 1

1.0

예제 입력 2

4
1 2 3 4
NYNN
NNYN
NNNY
NYNN

예제 출력 2

1.0

예제 입력 3

4
5 6 7 8
NYNN
YNNN
NNNY
NNYN

예제 출력 3

6.0

예제 입력 4

2
10 5
NY
NN

예제 출력 4

7.5

예제 입력 5

5
34 22 25 43 12
NYNNY
YNNYN
NNNYY
NNNNN
NNNNN

예제 출력 5

19.666666666666668

출처