이상한 커플
시간 제한8초메모리 제한512 MB
부호가 있는 교차로에서는 극장으로 가는 최단 경로를, 부호가 없는 교차로에서는 무작위로 이동하는 무향 가중 그래프에서 집에서 극장까지의 기대 이동 거리를 구한다.
문제
Alice와 Bob은 집에서 극장까지 차를 몰고 데이트를 하러 간다. 두 사람은 도전 정신이 강해서, 새 집으로 막 이사 와 길을 전혀 모르는데도 지도를 챙기지 않았다. 그저 감으로 가는 것이다.
두 사람이 달리는 마을은 교차로(정점)와 도로(간선)로 이루어진 무방향 그래프로 생각할 수 있다. 각 교차로에는 표지판이 있을 수도 있고 없을 수도 있다. 표지판이 있는 교차로에서 Alice와 Bob은 최단 경로에 해당하는 도로로 진입한다. 그러한 도로가 여러 개면 그중 하나를 무작위로 고른다.
표지판이 없는 교차로에서는 그냥 무작위로 고른다. 각각의 무작위 선택은 같은 확률로 이루어진다. 무작위 선택으로 방금 지나온 도로로 되돌아가는 것도 가능하다.
Alice와 Bob이 극장에 도착할 때까지 운전할 거리의 기댓값을 계산하라.
입력
입력은 다음 형식으로 주어진다.
n s t
q1 q2 ... qn
a11 a12 ... a1n
a21 a22 ... a2n
.
.
.
an1 an2 ... ann
n은 교차로의 수이다(n ≤ 100). s와 t는 각각 집과 극장이 있는 교차로이다(1 ≤ s, t ≤ n, s ≠ t). qi(1 ≤ i ≤ n)는 1 또는 0이며, 1은 i번째 교차로에 표지판이 있음을, 0은 없음을 나타낸다. aij(1 ≤ i, j ≤ n)는 i번째와 j번째 교차로를 잇는 도로의 거리를 나타내는 양의 정수이거나, 두 교차로를 직접 잇는 도로가 없음을 나타내는 0이다. 각 도로의 거리는 10을 넘지 않는다.
그래프는 무방향이므로 1 ≤ i, j ≤ n인 임의의 i, j에 대해 aij = aji이다. 같은 교차로를 잇는 도로가 있을 수 있다. 즉, 항상 aii = 0인 것은 아니다. 또한 그래프가 항상 평면 그래프인 것도 아니다.
출력
극장에 도착할 때까지 운전할 거리의 기댓값을 10-8의 오차 범위 내에서 출력하라. 극장에 도달하는 경로가 없으면 "impossible"(따옴표 제외)을 출력한다. 소수점 아래 자릿수는 얼마든지 좋다.