시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB0000.000%

문제

영수는 다음 주에 첫 출근을 앞두고 있다. 서울의 대중교통은 매우 잘 되어 있지만, 모종의 이유로 모든 교통수단이 검문을 받게 되었다. 영수는 첫 출근인 만큼 지각하지 않기 위해서 미리 회사로 가는 길목의 모든 교통편에 대한 스케쥴과 지연 예상 시간 등을 수집하였다. 과연 영수는 회사까지 가는데 얼마나 걸릴까?

각 교통 수단은 다음과 같이 정의된다. 

  • 출발지에서 항상 매시 S분에 출발하며, 도착지까지 가는데 걸리는 시간은 R분이다.
  • 각 차량은 이동 도중 경찰의 검문을 받는다. 검문은 즉각적으로 이루어지지만 P%의 확률로 문제가 있어서 D분 동안 지연될 수 있다. 검문은 D분 후에 다시 이루어지며 이때도 마찬가지로 문제가 있을 경우 또다시 지연될 수 있다. 이 검사는 통과할 때까지 무한히 반복될 수 있다.
  • 교통 수단에 탑승한 이후에는 도착지에 도착하기 전 중간에 내릴 수 없다.

또한, 영수가 집에서 출발하는 시간은 0이며, 어느 길목에서든지 도착시간의 기댓값을 최소화할 수 있는 교통수단을 선택한다.

입력

입력의 첫 줄에는 테스트 케이스의 숫자 T가 주어진다.
각 테스트 케이스는 다음과 같이 주어진다.

N M H O
A0 B0 S0 R0 D0 P0
...
AM-1 BM-1 SM-1 RM-1 DM-1 PM-1

각 케이스의 첫 줄에는 다음과 같이 정수 4개가 주어진다. N은 길목의 수, M은 교통 수단의 수를 나타낸다. 그리고 H는 집이 위치한 길목 번호이고, O는 회사가 위치한 길목 번호이다.
두 번째 줄부터 M개의 줄은 6개의 정수가 주어지며, 각각 교통 수단의 정보를 나타낸다. Ai는 교통 수단의 출발 길목 번호, Bi는 교통 수단의 도착 길목 번호이며, Si는 출발 시간, Ri는 이동 소요 시간이다. 그리고 Di는 지연시간, Pi는 지연확률이다. 지연 확률은 % 수치이다.

제한

  • 1 ≤ T ≤ 100.
  • 2 ≤ N ≤ 100.
  • 0 ≤ HOAiBi < N
  • 0 ≤ Si ≤ 59.
  • 1 ≤ Ri ≤ 100.
  • 1 ≤ Di ≤ 100.
  • 0 ≤ Pi ≤ 100.
  • 모든 i에 대해서 Ai != Bi 이다.
  • 모든 (i < j) 쌍에 대해서 Ai != Aj 또는 Bi != Bj 이다.
  • 0 ≤ M ≤ N * (N-1).
  • Small dataset과 같은 조건이 없다.

출력

각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이고, y는 도착하는 데 걸리는 시간의 기댓값이다. 10-6 범위의 절대/상대오차는 정답으로 간주된다. 만약 도착할 수 없다면 -1을 출력한다.

예제 입력 1

3
2 1 0 1
0 1 5 5 1 10
3 3 0 2
0 1 0 5 61 50
1 2 5 5 62 50
0 2 0 5 63 99
2 0 0 1

예제 출력 1

Case #1: 10.1111111
Case #2: 162.0000000
Case #3: -1

채점 및 기타 정보

  • 예제는 채점하지 않는다.