젊고 가난하고 바쁜 두 사람
시간 제한1초메모리 제한128 MB
하코다테와 도쿄에서 출발한 두 사람이 08시부터 18시 사이에 한 도시에서 30분 이상 만나고 각자 귀가하는 가장 싼 왕복 표를 구합니다.
문제
켄과 케이코는 아르바이트에 치여 사는 학생이라 시간도 돈도 넉넉하지 않다. 켄은 하코다테에 살고 케이코는 도쿄에 산다. 둘은 만나고 싶지만 같은 날 안에 각자의 일터로 돌아가야 하고, 차비도 아껴야 한다. 두 사람이 가장 싸게 만나는 방법을 찾아라.
켄은 하코다테에서, 케이코는 도쿄에서 출발한다. 두 사람은 모든 열차의 시각과 요금을 알고 있고, 각자 사는 도시를 포함해 어느 도시에서든 만날 수 있다. 다만 08:00보다 먼저 출발할 수 없고, 18:00까지는 각자의 도시로 돌아와야 한다. 환승에는 시간이 걸리지 않아서 도착한 그 분에 바로 다음 열차를 탈 수 있다. 두 사람은 같은 도시에서 30분 이상 함께 있으려고 한다.
시각표에는 도시가 최대 100개, 직통 노선이 최대 2000개 들어갈 수 있다. 가능한 일정을 하나씩 만들어 보는 방법으로는 제한 시간 안에 끝나지 않는다.
입력
입력은 여러 개의 데이터 집합으로 이루어진다.
각 데이터 집합의 첫 줄에는 시각표에 실린 노선의 개수를 나타내는 정수가 하나 주어진다. 이 값은 2000 이하이다.
이어지는 줄에는 노선이 한 줄에 하나씩 다음 형식으로 주어진다.
출발도시 HH:MM 도착도시 HH:MM 요금
도시 이름은 알파벳 16글자 이하이고 첫 글자만 대문자이다. 출발 시각과 도착 시각은 시와 분을 각각 두 자리로 적고 콜론으로 구분하며, 00:00부터 23:59까지이다. 도착 시각은 출발 시각보다 반드시 늦다. 노선 하나의 요금은 1 이상 10000 이하의 정수이다. 각 항목은 공백으로 구분한다.
숫자 0만 있는 줄이 나오면 입력이 끝난다.
출력
데이터 집합마다 가능한 최소 총요금을 한 줄에 출력한다. 이 값은 두 사람이 이용하는 모든 노선의 요금을 더한 것이다.
만날 방법이 없는 데이터 집합에는 0을 출력한다.