문제
수빈이는 크기가 무한대인 격자판 위에 살고 있다. 격자판의 각 점은 두 정수의 쌍 (x, y)로 나타낼 수 있다.
제일 처음에 수빈이의 위치는 (xs, ys)이고, 집이 위치한 (xe, ye)로 이동하려고 한다.
수빈이는 두 가지 방법으로 이동할 수 있다. 첫 번째 방법은 점프를 하는 것이다. 예를 들어 (x, y)에 있는 경우에 (x+1, y), (x-1, y), (x, y+1), (x, y-1)로 이동할 수 있다. 점프는 1초가 걸린다.
두 번째 방법은 텔레포트를 사용하는 것이다. 텔레포트를 할 수 있는 방법은 총 세 가지가 있으며, 미리 정해져 있다. 텔레포트는 네 좌표 (x1, y1), (x2, y2)로 나타낼 수 있으며, (x1, y1)에서 (x2, y2)로 또는 (x2, y2)에서 (x1, y1)로 이동할 수 있다는 것이다. 텔레포트는 10초가 걸린다.
수빈이의 위치와 집의 위치가 주어졌을 때, 집에 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.
# 12908
import sys
input = lambda : sys.stdin.readline().strip()
INF = sys.maxsize
start = list(map(int, input().split()))
end = list(map(int, input().split()))
tel1 = list(map(int, input().split()))
tel2 = list(map(int, input().split()))
tel3 = list(map(int, input().split()))
position = [start, end, tel1[:2], tel1[2:], tel2[:2], tel2[2:], tel3[:2], tel3[2:]]
graph = [[INF] * (9) for _ in range(9)]
graph[3][4], graph[4][3] = 10, 10
graph[5][6], graph[6][5] = 10, 10
graph[7][8], graph[8][7] = 10, 10
for i in range(1, 9):
for j in range(1, 9):
graph[i][j] = min(graph[i][j], abs(position[i-1][0] - position[j-1][0]) + abs(position[i-1][1] - position[j-1][1]))
graph[i][j] = graph[j][i]
for k in range(1, 9):
for a in range(1, 9):
for b in range(1, 9):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
print(graph[1][2])변수의 조건이 0이상 10^9 이하이다. 그렇기에 INF 값을 10^9 보다 큰 수로 지정해야 한다.
