페이지 전환 > 문제은행 : 정보올림피아드&알고리즘



1108 : 페이지 전환

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
647 회   
시도횟수
1320 회   

문제

인터넷이 발달하여 사람들이 웹서핑을 많이 하는데, 웹브라우져를 켜서 보통은 19번의 클릭을 한다고한다.


페이지를 전환하는 상태가 아래 그래프와 같이 주어진다면,
 

1번 페이지에서 2번, 3번, 4번 페이지로 갈 때의 가장 짧은 페이지 클릭 횟수는 1,1,2이고, 

2번 페이지에서 1번, 3번, 4번 페이지로 갈 때 가장 짧은 페이지 클릭 횟수는 3,2,1이고,

3번 페이지에서 1번, 2번, 4번 페이지로 갈 때 가장 짧은 페이지 클릭 횟수는 1,2,3이고, 

4번 페이지에서 1번, 2번, 3번 페이지로 가는 가장 짧은 페이지 클릭 횟수는 2,3,1이다.


이때, 가장 짧은 페이지 클릭 횟수의 합을 모두 구하면 1+1+2+3+2+1+1+2+3+2+3+1=22 이다.
이 그래프에서 모든 쌍은 1번에서 2번 페이지로 가기, 1번에서 3번 페이지로 가기, ..., 4번에서 3번 페이지로 가기, 
12쌍이 나오기 때문에 어떤 페이지에서 다른 페이지로 이동하는 평균 클릭 횟수는 22/12로 1.833이된다.


입력형식

첫줄에 N(1≤N≤500)이 나온다. 

다음줄부터 N개의 줄 각각에 i, j가 나오는데 이것은 i페이지에서 j페이지로 갈 수 있음을 의미한다. 

또한 단 방향이므로, j에서 i로는 갈 수 없다. j에서 i로 갈 수 있으려면, 뒤의 줄에 j, i가 나와야 한다. 

이때, 어떤 페이지에서 다른 페이지로 갈 수 없는 경우는 없도록 데이터가 입력된다.

또한 페이지의 번호는 1번 부터 i, j 값중 가장 큰 값이 페이지의 마지막 번호로 들어온다. 

 

단, 페이지 번호는 500보다 작은 수이다.


출력형식

출력은 어떤 페이지에서 다른 페이지로 이동하는 평균 클릭 횟수를 출력한다. 

출력값으로는 소수 넷째자리에서 반올림하여 소수 셋째자리까지 출력한다.


입력 예

5
1 2
2 4
1 3
3 1
4 3

출력 예

1.833

최단거리

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP