알고리즘 문제 하나(AVOID)

출처 : http://algospot.com/judge/problem/read/AVOID

문제

 

대학의 축제 기간인 5월이 되면 캠퍼스는 놀자판으로 바뀝니다. 대학원 석사 과정 1학기인 현환이는 교수님 몰래 연구실을 빠져나와 축제를 즐기려고 합니다. 다행히도 오늘 교수님은 교내의 다른 건물에서 중요한 회의가 있어 연구실에 오시지 않을 것이기 때문에 현환이는 안심했습니다. 그러나 교수님이 회의를 하고 나서 교문으로 가시는 길에 현환이를 보게 된다면 꼼짝 못하고 교수님에게 귀를 잡혀 연구실로 다시 끌려가게 될 것입니다.

교내는 여러 개의 지점들과 그들을 잇는 양방향 도로들로 구성되며, 각 도로에는 분 단위로 소요되는 시간이 주어집니다. 교수님은 이성적인 분이시기 때문에 항상 최단 경로를 따라 움직입니다만, 최단 경로가 두 개 이상 있을 때는 각 경로를 동일한 확률로 선택해서 움직이십니다.

현환이는 축제에서 가 보고 싶은 몇 군데의 지점이 있습니다. 이 각각의 지점마다 교수님이 지나갈 확률을 계산하는 프로그램을 작성하세요.