영국 아일랜드 여행

문제 정보

문제

알고스팟 대회의 단골 출제위원 태윤이는 지금 영국과 아일랜드를 여행하고 있다. 태윤이는 여행을 떠나기에 앞서, 가고 싶은 여행지 N개를 골랐다. 그리고 각 여행지에 1부터 N까지 번호를 붙였고, 인접한 여행지 사이에 거리를 기록해 여행지도를 만들었다. (역시 프덕후!)

태윤이의 이번 여행은 런던(1번 여행지)에서 시작해 더블린(N번 여행지)에서 끝난다. 그리고 그사이에 가게 될 여행지는 아래와 같은 방법으로 결정한다.

태윤이는 현재 위치를 떠날 때마다, 인접한 모든 여행지를 확인한다. 현재 위치부터 더블린까지의 최단거리보다 인접한 여행지부터 더블린까지의 최단거리가 더 짧다면, 그곳은 이동 가능한 여행지다.

이동 가능한 여행지를 뽑은 후에는, 그중에 현재 위치에서 가장 가까운 여행지부터 순위를 매긴다. 거리가 같다면 번호가 작은 여행지가 더 높은 순위를 가진다. 이동 가능한 여행지 P개가 있다면, 1위는 50%, 2위는 25%, 3위는 12.5% ... P위는 100/2P% 확률로 다음 여행지를 결정하고 이동한다. 이동한 후에는 다시 또 그다음 여행지를 고민하기 시작한다……. 아! 그리고 나머지 100/2P% 확률로는 아이스크림을 하나 사 먹고, 더 이상 고민 없이 현재 위치에서 최단경로로 더블린까지 쭉 간다. 거리가 같은 최단경로가 여러 개 있다면, 매 순간 그중 가장 번호가 작은 여행지로 이동한다.

입력으로 여행 지도와 Q개의 여행지 번호가 주어진다. Q개의 여행지에 대해, 태윤이가 여행 도중 지나갈 확률을 구하라.

입력

입력은 T 개의 테스트 케이스로 구성된다. 입력의 첫 줄에는 T가 주어진다.

각 테스트 케이스의 첫 줄에는 여행지의 개수 N과 인접한 여행지들을 잇는 길의 개수 M이 주어진다.(2 <= N <= 10000, 1 <= M <= 30000) 그 후 M줄에 각각 길의 정보로써 인접한 두 여행지의 번호 Vi, Ui와 길의 거리를 나타내는 정수 Di가 주어진다.(1 <= Vi < Ui <= N, 1 <= Di <= 100) 인접한 두 여행지는 양쪽에서 서로 이동이 가능하다. 즉, Vi에서 Ui로 이동할 수도 있고, Ui에서 Vi로도 가능하다. 또한, 두 여행지 사이에는 길이 두 개 이상 존재하지 않는다.
그다음 줄에는 확률을 계산해야 할 여행지의 개수 Q가 주어지고, 그다음 줄에는 Q개의 여행지 번호 Bi가 주어진다. (1 <= Q <= 100, 1 <= Bi <= N)

런던에서 더블린으로 가는 길은 항상 하나 이상 존재한다.

출력

각 테스트 케이스마다 한 줄에 Q개씩, 각 도시에 대해 태윤이가 여행 도중 지나갈 확률을 공백으로 구분하여 출력한다. 1e-8 이내의 절대/상대 오차는 정답으로 인정된다. 그러므로 소수점 이하 8자리 이상 출력하기를 권장한다.

예제 입력

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

예제 출력

1 0.75 1
1 0.625 0.75 0 1

노트

0개의 댓글이 있습니다.