python 백준 16958 텔레포트

https://www.acmicpc.net/problem/16958

주의

• 알고리즘 분류에 플로이드 워셜로 되어 있음
• 플로이드 워셜 알고리즘을 이용하여 계산시 전체 노드를 대상으로 할 경우 너무 많은 계산이 발생함
• 이 문제에서 각 node 사이의 거리는 다른 지점에 들려도 좁아지지 않는 그래프
• 따라서 텔레포트를 이용하지 않는 한 거리가 좁혀질수가 없음

로직

• 각 node의 row, colum을 기록
• 텔레포트가 가능한 node의 경우 따로 기록
• 저장된 row,colum을 이용하여 node끼리의 거리를 구하고 저장
• 각 node에서 텔레포트가 가능한 node 중 가장 가까운 곳까지의 거리를 기록
• 기존의 node1과 node2사이의 거리와 node1에서 텔레포트 지점 + node2에서 텔레포트 지점 중 가까운 값으로 거리 갱신

import sys
input = sys.stdin.readline
# 거리 구하는 함수
def length(c1:tuple,c2:tuple)->int:
    return abs(c1[0] - c2[0]) + abs(c1[1]-c2[1])

N,T = map(int,input().split())
city = [] #각 node의 좌표 기록
specialCity = set() #텔레포트 가능한 node 기록
for idx in range(N):
    s,x,y = map(int,input().split())
    city.append((x,y))
    if s:
        specialCity.add(idx)
INF = 10000

graph = [[INF]*(N) for _ in range(N)]
# 자기 자신으로 이동은 0, 생각해보니 이 코드에선 구조에서는 필요가 없는듯
for idx in range(N):
    graph[idx][idx] = 0
# 각 node 사이의 거리 측정 후 기록
for s in range(N):
    for e in range(s+1,N):
        l = length(city[s],city[e])
        graph[s][e] = l
        graph[e][s] = l
# 각 node와 텔레포트가 가능한 node 사이의 거리 기록
short_cut = [0]*(N)
for c in range(N):
    if c in specialCity:
        continue
    minValue = 10000
    for node in specialCity:
        minValue = min(minValue,graph[c][node])
    short_cut[c] = minValue

# 기존의 거리와 텔레포트를 이용한 거리중 짧은 값으로 갱신
for s in range(N):
    for e in range(s+1,N):
        graph[s][e] = min(graph[s][e],short_cut[s]+short_cut[e]+T)
        graph[e][s] = graph[s][e]

M = int(input())
for _ in range(M):
    a,b = map(int,input().split())
    print(graph[a-1][b-1])