Bancopia

Bancopia에서는 강도 사건이 잦아 금괴 수송이 위험하며, 어떤 도로는 다른 도로보다 더 위험하다. 두 도시 사이에서 금괴를 안전하게 옮기기 위해, Bancopia는 일부 도로에 경찰 초소를 세워 그 도로를 더 안전하게 만들려고 한다.

주어지는 것은 Bancopia의 도시들, 도시들을 잇는 도로들, 그리고 금괴 수송이 이루어지는 두 도시이다. 각 도로에는 강도 확률이 있다. 이는 금괴 수송이 그 도로를 지날 때 그 도로에서 강도를 당할 확률을 뜻한다. 서로 다른 도로에서 강도를 당하는 사건은 서로 독립이라고 가정한다.

또한 설치할 수 있는 경찰 초소의 최대 개수가 주어진다. 한 도로에는 초소를 최대 한 개만 세울 수 있으며, 경찰 초소는 그 도로의 강도 확률을 정확히 절반으로 줄인다.

수송은 항상 두 도시 사이의 가장 안전한 경로, 즉 전체 강도 확률이 가장 작은 경로를 택한다. 어떤 경로가 (절반으로 줄었을 수도 있는) 강도 확률 $p_1, p_2, \dots, p_k$ 인 도로들을 지난다면, 그 경로의 전체 강도 확률은 $1 - \prod_{i=1}^{k}(1 - p_i)$ 이다.

가장 안전한 경로의 강도 확률이 최소가 되도록 경찰 초소를 배치했을 때, 그 최소 확률을 구하라.

첫 번째 줄에는 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 한 줄에 다섯 정수 $n$, $w$, $m$, $a$, $b$가 공백으로 구분되어 주어진다. 여기서 $2 \le n \le 100$ 은 도시의 수, $1 \le w \le 10^4$ 은 도로의 수, $1 \le m \le 100$ 은 설치할 수 있는 경찰 초소의 최대 개수이며, $a$와 $b$는 수송이 이루어지는 두 도시이다. 도시는 ${1, \dots, n}$ 의 서로 다른 정수로 번호가 매겨진다.
• 이어지는 $w$개의 줄에 각 도로가 하나씩 주어진다. 각 줄에는 세 값 $s_1$, $s_2$, $p$가 공백으로 구분되어 주어지며, $s_1$과 $s_2$는 도로가 잇는 두 도시($s_1 \ne s_2$, $1 \le s_1, s_2 \le n$), $0 \le p \le 1$ 은 그 도로의 강도 확률이다.

같은 도시 쌍을 잇는 도로가 두 개 이상 주어지지는 않는다. 모든 도로는 양방향이며, 진행 방향에 관계없이 강도 확률이 같다. $a$에서 $b$로 가는 경로가 적어도 하나 존재함이 보장된다.

각 테스트 케이스마다 한 줄에 하나의 수를 출력한다. 이 수는 강도 확률이 최소가 되도록 경찰 초소를 최대 $m$개까지 배치했을 때 $a$에서 $b$까지 가장 안전한 경로의 강도 확률이며, 소수점 아래 넷째 자리까지 반올림하여 출력한다. 반올림은 통상적인 방식(반올림, round half up)을 따른다. 즉 $0.12345\ldots$ 는 $0.1235$ 로, $0.12344\ldots$ 는 $0.1234$ 로 반올림한다.

그림 1: 지도는 한 가지 상황을 보여준다. 왼쪽 지도는 경찰 초소가 없을 때의 가장 안전한 경로이고, 오른쪽 지도는 초소를 배치한 뒤의 가장 안전한 경로이다. 각 도시에는 번호가 매겨져 있고, 각 도로 옆에는 그 도로의 강도 확률이 적혀 있다. 도착 도시 옆에는 경로 전체의 강도 확률이 적혀 있다.