dlaud5379   1년 전

(DeepL로 영어로 번역한 텍스트를 중역했습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

잇창명은 프로그래밍을 하던 도중 박한별에게 전화로 도움 요청을 받았다. 박한별은 여러 개의 방이 있고 길로 연결되어 있는 동굴에 갇혀 있다. 한 방에서 직접 연결되어 있는 다른 방으로 걸어가는 데는 정확히 1초가 걸린다. 박한별은 여러 개의 방 중 한 곳에 있고, 출구까지 얼마나 빨리 도착할 수 있는지 궁금해하고 있다. 2EZ라고 생각하면서 생각나는 최단 경로 알고리즘을 구현하려던 잇창명은 박한별에게 텔레포트 이능력이 있다는 것을 기억해낸다!

박한별은 정점이 n개, 간선이 m개인 무향 그래프의 s번 정점에 있고, 출구는 t번 정점에 있다. 박한별은 매 초마다 인접한 정점으로 걸어가거나 텔레포트를 할 수 있다. 텔레포트를 할 경우 그래프의 모든 정점 줌 한 곳에 균등한 확률로 도착한다(즉, 1 ≤ i ≤ n번 정점에 대해 i번 정점에 도착할 확률은 1/n이다). 박한별이 t번 정점에 도달할 수 있는 최소 기대 시간을 구하여라.

기대 시간의 엄밀한 정의는 다음과 같다. 박한별이 어떤 전략을 정하고 그 전략대로 행동했을 때 t번 정점에 정확히 i초만에 도착할 확률이 pi라고 할 때, 그 전략의 기대 시간은 1·p1 + 2·p2 + 3·p3 + ...이다. 두 정점 사이를 왔다갔다만 하는 등의 매우 나쁜 전략을 선택한다면 기대 시간이 무한히 커질 수 있지만, 기대 시간이 유한한 전략이 항상 존재함을 보일 수 있다. 예를 들어, 매 초 무조건 텔레포트를 하는 전략의 기대 시간은 n이다.

입력

첫째 줄에 n과 m이 주어진다. (2 ≤ n ≤ 105, 0 ≤ m ≤ 105)

둘째 줄에 시작 정점과 도착 정점의 번호 s와 t가 주어진다. (1 ≤ s, t ≤ n, s ≠ t)

셋째 줄부터 m줄에 걸쳐 간선의 정보가 한 줄에 하나씩 주어진다. 각 간선은 ui와 vi로 주어지며, ui번 정점과 vi번 정점을 잇는 간선이 존재한다는 의미이다. (1 ≤ ui, vi ≤ n, ui ≠ vi)

출력

도착 정점에 도달할 수 있는 최소 기대 시간을 한 줄로 출력한다. 절대 오차 또는 상대 오차가 10-2 이하이면 정답이다.

예제 설명 1

도착 정점까지 2초에 걸쳐 걸어가는 것이 최적의 전략이므로 최소 기대 시간은 2이다.

예제 설명 2

주어진 그래프에 간선이 없으므로 텔레포트밖에 할 수 없으며, 이때의 기대 시간은 n이다.

예제 설명 3

4번 정점에서는 텔레포트를 하고, 1번과 3번 정점에서는 도착 정점까지 걸어가는 것이 최적의 전략이다.

댓글을 작성하려면 로그인해야 합니다.