10894번 - Following Flow 스페셜 저지

세상은 N+1개의 정점으로 이루어져 있는데, 각 정점은 0에서 N까지의 번호가 붙어있다. 각 정점에서는 다른 정점으로 가는 간선이 있는데, 각 간선은 일방통행이며, 각 간선마다 간선을 지나가는데 걸리는 시간이 다르다. 동현이는 세상을 떠돌고 있는데, 0번 지점은 동현이가 현재 있는 위치이고, N번은 동현이의 집이다. 동현이는 집에 도착하기 전까지는 마음이 가는 대로 세상을 떠돌고 싶어한다. 마음이 가는 대로라는 것은 현재 정점에서 다른 정점으로 갈 수 있는 모든 간선에 대해 동일한 확률로 한 간선을 선택하여 다음 정점으로 가는 것이다. 이때 동현이는 집으로 가기까지 걸리는 시간의 기댓값이 어느 정도 일지 궁금하다. 예를 들어 세상이 다음과 같이 이루어져 있다고 생각해보자.

다음과 같은 경우 처음에 동현이는 0번 지점에서 각각 50%의 확률로 1초가 걸려 1번 지점으로 이동하거나 1초가 걸려 2번 지점으로 이동하여 집에 도착하게 된다. 1번 지점으로 가는 경우 역시 50%의 확률로 3초가 걸려 0번 지점으로 돌아오거나 3초가 걸려 2번 지점으로 이동하여 집에 도착하게 된다. 이 경우 답은 아래와 같다.

1/2 × 1 + (1/2)² × (1 + 2) + (1/2)³ × (1 + 2 + 1) + ⋯ = 8/3

첫 번째 줄에는 정점의 개수를 나타내는 N (1 ≤ N ≤ 30)과 간선의 개수를 나타내는 M (1 ≤ M ≤ 1,000)이 공백으로 구분되어 주어진다. (실제 정점 개수는 N+1임에 주의하라)

다음 M개의 줄에는 각 줄마다 x, y, t (0 ≤ x < N, 0 ≤ y < N, 1 ≤ t ≤ 50)가 공백으로 구분되어 주어지는데, x에서 y로 가는 간선이 있고 가는데 시간이 t만큼 걸린다는 뜻이다. 어떤 정점에서든 정점 N으로 가는 길이 있도록 간선이 주어진다.

정점 0에서 출발하여 집 (정점 N) 에 도착할 때까지 걸리는 시간의 기댓값을 출력하라. 답과의 절대 혹은 상대 오차가 10⁻⁶ 이하라면 정답으로 인정된다. 답은 10⁶ 을 넘지 않음이 보장된다.