발렌시아의 달
시간 제한1초메모리 제한128 MB
만족도가 있는 장소와 도보 경로로 이루어진 지도에서, 시간 제한을 만족하면서 목표 만족도와 차이가 0.1 미만인 단순 경로가 존재하는지 각 질의마다 판별하는 문제입니다.
문제
발렌시아의 달에는 마법이 깃들어 있다고들 한다. 밤사이 벌어지는 신비한 일을 두고 다들 한마디씩 보탠다. 사람들은 첫 술집에 몇 시에 들어갔는지, 호텔에 몇 시에 도착했는지, 도착했을 때 얼마나 만족스러웠는지는 기억한다. 그런데 그사이 어느 바와 펍을 거쳤는지는 아무도 기억하지 못한다.
발렌시아의 호텔들이 손님의 기억을 되살려 줄 프로그램을 당신에게 맡겼다. 손님은 출발 시각과 출발 장소, 도착 시각과 도착 장소, 도착했을 때의 만족도를 알려 준다. 프로그램은 그 이야기와 맞아떨어지는 밤이 실제로 가능한지 판단한다.
프로그램은 바와 펍의 위치가 적힌 지도를 쓴다. 어떤 장소에 들어가면 그 장소의 만족도만큼 만족도가 오른다. 반대로 장소 사이를 걸으면 사람은 짜증이 나므로 만족도가 내려간다. 걷는 데 걸린 시간 1분마다 만족도가 1씩 줄고, 분으로 딱 떨어지지 않으면 남는 초도 분의 일부로 센다. 즉 30초는 0.5분이다. 걷는 속도는 모두 시속 4km다. 바나 펍에는 원하는 만큼 머물러도 되지만, 만족도를 얻으려면 적어도 15분은 있어야 한다.
지나는 장소에 모두 들어갈 필요는 없다. 경로 위의 장소 중 일부만 골라 들어가도 되고, 출발 장소에 들어가는 것도 선택이다. 만족도는 도착 장소의 문 앞까지만 계산하므로 도착 장소의 만족도는 절대 더하지 않는다. 한 장소를 두 번 지나는 경로는 쓸 수 없다.
밤은 출발 시각과 도착 시각 사이에 모두 들어가야 한다. 걷는 데 쓴 시간에 들어간 장소마다 15분씩 더한 값이 그 사이 시간을 넘으면 안 된다. 시간이 남으면 들어간 가게에 더 앉아 있으면 되므로 남는 시간은 문제가 되지 않는다.
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스는 지도 설명으로 시작하고, 뒤이어 확인해야 할 도착 목록이 온다.
지도 설명은 대문자 MAP과 두 정수 , 으로 시작한다. 는 장소의 수, 은 두 장소를 잇는 길의 수다 (). 다음 줄에는 장소가 한 줄에 하나씩 주어지며, 각 줄에는 좌표 두 개(킬로미터 단위의 실수), 그 장소의 만족도(실수), 아이디, 이름이 차례로 적혀 있다. 이어지는 줄에는 길이 한 줄에 하나씩 주어지며, 그 길이 잇는 두 장소의 아이디가 적혀 있다. 두 장소를 잇는 길은 많아야 하나이고, 서로 교차하는 길은 없다.
지도 다음에는 대문자 ARRIVALS만 적힌 줄이 오고, 그 뒤로 도착이 한 줄에 하나씩 주어진다. 각 줄에는 출발 시각, 출발 장소, 도착 시각, 도착 장소, 도착했을 때의 만족도(실수)가 적혀 있다. 시각은 24시간제 hh:mm 형식이며, 도착 시각이 출발 시각보다 앞서면 자정을 넘겨 도착했다는 뜻이다.
출력
각 케이스마다 대문자 MAP과 케이스 번호를 적은 줄을 먼저 출력한다. 첫 번째 케이스는 MAP 1, 두 번째는 MAP 2와 같이 센다.
그다음 입력에 주어진 순서대로 도착마다 한 줄씩 출력한다. 손님의 이야기와 맞는 경로가 하나라도 있으면 Possible!을, 하나도 없으면 Impossible!을 출력한다.
경로가 이야기와 맞으려면 지도의 길만 따라가야 하고, 같은 장소를 두 번 지나지 않아야 하며, 출발 시각과 도착 시각 사이에 들어가야 하고, 얻은 만족도와 요구된 만족도의 차이의 절댓값이 0.1보다 작아야 한다.
탐색은 최대한 빠르게 돌아가도록 짜라. 예제 케이스가 좋은 기준이다. 예제를 여유 있게 처리하면 나머지도 처리한다.
힌트
그림 1: 예제 입력의 첫 번째 지도.