시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 0 | 0 | 0 | 0.000% |
영수는 다음 주에 첫 출근을 앞두고 있다. 서울의 대중교통은 매우 잘 되어 있지만, 모종의 이유로 모든 교통수단이 검문을 받게 되었다. 영수는 첫 출근인 만큼 지각하지 않기 위해서 미리 회사로 가는 길목의 모든 교통편에 대한 스케쥴과 지연 예상 시간 등을 수집하였다. 과연 영수는 회사까지 가는데 얼마나 걸릴까?
각 교통 수단은 다음과 같이 정의된다.
또한, 영수가 집에서 출발하는 시간은 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는 지연확률이다. 지연 확률은 % 수치이다.
각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이고, y는 도착하는 데 걸리는 시간의 기댓값이다. 10-6 범위의 절대/상대오차는 정답으로 간주된다. 만약 도착할 수 없다면 -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
Case #1: 10.1111111 Case #2: 162.0000000 Case #3: -1
Contest > Google > Google's Coding Competitions > Google Code Jam Korea 2012 > Code Jam Korea 2012 결선 라운드 C2번