1220번 - MEGACITY 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 377 | 128 | 35 | 19.886% |
문제
신도시 MegaCity의 모든 도로는 가로 방향과 세로 방향으로 되어 있으며, 인접한 수평 도로들 사이의 간격과 인접한 수직 도로들 사이의 간격은 모두 동일하다. 수평 도로 i와 수직 도로 j가 만나는 곳의 좌표를 (i, j)라고 하자. 도로들로 구성되는 블록들의 한 변의 길이를 1이라고 하면 도시의 두 위치 (a, b)와 (c, d) 사이를 연결하는 경로들의 길이 중에서 최솟값은 |a - c| + |b - d|이다.
이 도시의 상가 지역은 항상 차량으로 북적대기 때문에 차로 이동하는 데 시간이 더 소요된다. 각 상가 지역은 직사각형 영역이고, 각 블록을 이동하는 데 걸리는 시간은 상가 지역마다 차이가 있다. 자동차로 이동할 때, 비 상가 지역을 지나는 것이 대체로 유리하기는 하지만, 경우에 따라서는 상가 지역을 통과하는 것이 유리하기도 하다. 따라서 목적지까지 가장 빨리 가기 위한 경로를 찾는 것이 요구된다. 앞으로 출발지에서 목적지까지의 소요 시간이 가장 작은 경로를 가장 빠른 경로라고 부르자.
예를 들어 아래 그림을 보자. 비 상가 지역의 경우 블록 한 변을 이동하는데 걸리는 시간을 10이라고 하고, 각 상가 지역 A, B, C, D의 블록 한 변 이동 시간을 각각 44, 33, 22, 11이라고 하자. 그러면 두 위치 (1, 6)과 (15, 3) 사이의 가장 빠른 경로는 그림에서 표시된 것과 같이 총 길이가 19, 총 소요 시간이 192인 경로이다. 반면에 상가 지역을 전혀 통과하지 않는 경로 중 가장 빠른 경로는 길이가 21이며 총 소요 시간이 210이다.
MegaCity에서 주어진 두 지점 사이의 가장 빠른 경로의 소요 시간을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 네 개의 정수 a, b, c, d가 주어진다, 여기서 (a, b)는 출발지의 좌표이고 (c, d)는 도착 지점의 좌표이다, (a, b) ≠ (c, d). 둘째 줄에는 상가 지역의 개수를 나타내는 정수 n (0 ≤ n ≤ 1,000)이 주어진다. 그 다음 n개의 줄에는 각 줄마다 각 상가 지역인 직사각형 영역을 나타내는 네 개의 정수 lx, ly, hx, hy와 한 칸 이동 시간을 나타내는 정수 t (10 ≤ t ≤ 10^8)가 주어진다, 여기서 (lx, ly)는 직사각형의 왼쪽 아래 꼭짓점 좌표이고 (hx, hy)는 오른쪽 위 꼭짓점 좌표이다. 모든 좌표는 0 이상 10^8 이하의 정수이다. 둘 이상의 상가 지역이 서로 교차하거나 경계가 접하는 경우는 존재하지 않으며, 비 상가 지역의 블록 한 칸 이동 시간은 항상 10이라고 가정하시오.
출력
첫째 줄에 출발지와 도착지 사이의 가장 빠른 경로의 소요 시간을 출력한다.
예제 입력 1
1 6 15 3 4 2 1 3 7 44 5 2 10 4 33 8 5 11 9 22 12 1 14 8 11
예제 출력 1
192
출처
ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2008 D번
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호