1. 문제 설명

텔레포트

2. 문제 분석

플로이드-워셜 알고리즘을 통해 특정 노드를 경로로 사용해 각 노드에서 다른 모든 노드에 대한 최단 거리를 구한다.

• 플로이드-워셜을 푸는 알고리즘보다도 input() 등 입출력 함수 사용으로 인해 시간 초과가 난 문제다. sys.stdin.readline() 등으로 바꿔주고, 입력한 INF 초깃값도 다소 작은 수로 바꿔준 뒤 pypy로 통과했다.

3. 나의 풀이

from collections import deque
import sys

n, t = map(int, sys.stdin.readline().rstrip().split())
teleportable = [0 for _ in range(n)]
positions = [[] for _ in range(n)]
for i in range(n):
    teleport, row, col = map(int, sys.stdin.readline().rstrip().split())
    teleportable[i] = teleport
    positions[i] = [row, col]
    # 노드 별 좌표와 텔레포트 가능 여부 저장
INF = 10000
nodes = [[INF for _ in range(n)] for _ in range(n)]

for i in range(n):
    for j in range(n):
        if i == j: nodes[i][j] = 0
        else:
            i_pos = positions[i]
            j_pos = positions[j]
            distance = abs(i_pos[0] - j_pos[0]) + abs(i_pos[1] - j_pos[1])
            if teleportable[i] == 1 and teleportable[j] == 1 and t < distance: distance = t
            nodes[i][j] = distance
            # 각 노드별 거리 초깃값 기록. 텔레포트 가능한 도시일 때 맨해튼 거리와 비교해서 최단 거리를 입력

# 플로이드-워셜 알고리즘으로 각 노드에서 다른 모든 노드로 가는 최단 거리를 구한다.

for k in range(n):
    for i in range(n):
        for j in range(n):
            if nodes[i][j] > nodes[i][k] + nodes[k][j]:
                nodes[i][j] = nodes[i][k] + nodes[k][j]

m = int(input())
for _ in range(m):
    start, end = map(int, sys.stdin.readline().rstrip().split())
    print(nodes[start-1][end-1])