제설 작업

시간 제한1초메모리 제한128 MB

요약

양방향 도로의 모든 차선을 제설한 뒤 차고로 돌아오는 최소 시간을 구한다. 이미 제설된 차선에서는 더 빠르게 이동할 수 있다.

난이도: 어려움10점 중 8점
유형: 그래프, 최단 경로, 동적 계획법, 비트 연산
정답자: 아직 제출이 없습니다

문제

눈이 내리는 계절이 되면 도시는 제설 작업을 준비한다. 예산이 삭감되어, 이 도시에는 제설차가 단 한 대뿐이다. 제설차는 한 번 지나갈 때 도로의 차선 하나만 치울 수 있다. 눈이 쌓이면 제설차는 차고에서 출발해 도시를 돌며 눈을 치운다. 모든 도로의 모든 차선을 치우는 데 필요한 최소 시간은 얼마인가?

입력

첫 번째 줄에는 정수 두 개, 즉 차고의 x, y 좌표(단위: 미터)가 주어진다. 그 뒤로 최대 100개의 줄이 이어진다. 각 줄에는 한 도로의 시작점과 끝점 좌표(단위: 미터)가 주어진다. 모든 도로는 완전한 직선이며, 각 방향마다 차선이 하나씩 있다. 제설차는 어떤 교차로에서도 원하는 방향으로 방향을 바꿀 수 있고(U턴 포함), 도로의 끝에서 되돌아갈 수 있다. 제설차는 눈을 치우며 달릴 때는 시속 20 km, 이미 치운 차선을 달릴 때는 시속 50 km로 이동한다. 차고에서 모든 도로에 도달할 수 있다.

출력

모든 차선의 눈을 치우고 차고로 돌아오는 데 필요한 시간을 시와 분으로 출력한다. 시와 분은 콜론(:)으로 구분하며(예: 3:55), 분은 항상 두 자리로 표기한다. 시간은 분 단위로 반올림한다.

예제8

예제 1

입력

0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000

예상 출력

3:55

예제 2
입력
```
0 0
0 0 1000 0
```
예상 출력
```
0:06
```
예제 3
입력
```
0 0
0 0 10000 0
```
예상 출력
```
1:00
```
예제 4
입력
```
99999 99999
0 0 10000 0
```
예상 출력
```
1:00
```

예제 5

입력

-5000 -5000
-2000 -8000 -2000 8000

예상 출력

1:36

예제 6

입력

0 0
0 0 3000 4000
3000 4000 3000 9000

예상 출력

1:00

예제 7

입력

10 20
0 0 7000 0
7000 0 7000 3000
7000 3000 0 3000
0 3000 0 0

예상 출력

2:00

예제 8
입력
```
0 0
0 0 20000 10000
```
예상 출력
```
2:14
```