Avoid Your Professor
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- 출처
- 분류
문제
대학의 축제 기간인 5월이 되면 캠퍼스는 놀자판으로 바뀝니다. 대학원 석사 과정 1학기인 현환이는 교수님 몰래 연구실을 빠져나와 축제를 즐기려고 합니다. 다행히도 오늘 교수님은 교내의 다른 건물에서 중요한 회의가 있어 연구실에 오시지 않을 것이기 때문에 현환이는 안심했습니다. 그러나 교수님이 회의를 하고 나서 교문으로 가시는 길에 현환이를 보게 된다면 꼼짝 못하고 교수님에게 귀를 잡혀 연구실로 다시 끌려가게 될 것입니다.
교내는 여러 개의 지점들과 그들을 잇는 양방향 도로들로 구성되며, 각 도로에는 분 단위로 소요되는 시간이 주어집니다. 교수님은 이성적인 분이시기 때문에 항상 최단 경로를 따라 움직입니다만, 최단 경로가 두 개 이상 있을 때는 각 경로를 동일한 확률로 선택해서 움직이십니다.
현환이는 축제에서 가 보고 싶은 몇 군데의 지점이 있습니다. 이 각각의 지점마다 교수님이 지나갈 확률을 계산하는 프로그램을 작성하세요.
입력
입력의 첫 번째 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 지점의 수 V (2 <= V <= 100)과 도로의 수 E (0 <= E <= V(V-1)/2), 그리고 현환이가 가 보고 싶은 장소의 수 N (1 <= N <= V ) 가 주어집니다. 그 다음으로 E 줄에 각 3개의 정수로 각 도로가 잇는 두 개의 장소 A, B의 번호와 (1 <= A,B <= V ) 도로를 통행하는 데 걸리는 시간 T 가 분 단위로 주어집니다. 모든 소요 시간은 1 에서 10,000 사이의 자연수입니다. 마지막 줄에는 N 개의 정수로 가보고 싶은 장소의 번호가 1 부터 V 사이의 정수로 주어집니다. 교수님은 항상 1번 장소에서 출발해 V 번 장소로 가십니다.
출력
각 테스트 케이스마다 N 줄을 출력하되,입력에 주어진 각 장소에 대해 순서대로 교수님이 지나치실 확률을 출력 합니다. 확률은 항상 약분된 형태의 기약분수로 출력되어야 하며, a/b 의 꼴로 출력합니다.
예제 입력
2 4 4 2 1 2 1 1 3 1 2 4 1 3 4 1 2 4 8 10 4 1 2 1 2 4 1 1 3 1 3 4 1 1 4 2 4 5 2 5 7 1 5 8 3 4 6 1 6 8 4 2 4 5 7
예제 출력
1/2 1/1 1/3 1/1 1/2 0/1
노트
