백준|1238번|파티

문제 설명

각 마을 간의 거리를 입력받고 모든 마을에서부터 특정한 하나의 마을까지의 왕복 거리를 구한다고 할 때, 가장 긴 왕복 거리를 출력하는 문제입니다.

작동 순서

1. 마을의 수와 길의 개수, 목표지점이 되는 마을의 번호를 입력받습니다.
2. 각 마을 간의 거리를 입력받습니다. 이때 가는 길과 돌아오는 길의 거리 2가지를 구해야 하므로 시작점과 도착점을 바꿔가며 2개의 배열에 저장합니다.
3. 다익스트라 알고리즘을 사용하여 목표지점에서부터 다른 마을로 가는 거리를 구합니다.(목표지점에서 원래 위치로 돌아가는 거리를 구하는 과정입니다.)
4. 다익스트라 알고리즘을 사용하여 목표지점에서부터 다른 마을로 가는 거리를 구합니다. 이때 3번과는 다르게 출발점과 도착점이 바뀐 배열을 사용합니다.(시작점과 도착점을 바꾼 뒤 거리를 구하면 원래 위치에서 목표지점으로 돌아가는 거리를 구할 수 있습니다.
5. 목표지점으로 가는 거리와 원점으로 돌아오는 거리를 더한 뒤 가장 큰 값을 출력합니다.

소스코드

import heapq
import sys


def getDistance(route, node):
    heap = []
    time = [-1 for _ in range(N+1)]
    time[node] = 0
    for i in range(N+1):
        if route[node][i] != 101:
            heapq.heappush(heap, [route[X][i], i])

    while heap:
        t, d = heapq.heappop(heap)
        if time[d] == -1:
            time[d] = t
        else:
            continue
        for i in range(N+1):
            if time[i] == -1 and route[d][i] != 101:
                heapq.heappush(heap, [t+route[d][i], i])
    return time


N, M, X = map(int, sys.stdin.readline().split())

to_party = [[101 for _ in range(N+1)] for _ in range(N+1)]
to_home = [[101 for _ in range(N+1)] for _ in range(N+1)]
maxTime = -1

for m in range(M):
    s, d, t = map(int, sys.stdin.readline().split())
    to_party[s][d] = min(to_party[s][d], t)
    to_home[d][s] = min(to_home[d][s], t)

go_time = getDistance(to_party, X)
back_time = getDistance(to_home, X)

for i in range(N+1):
    if maxTime < go_time[i]+back_time[i]:
        maxTime = go_time[i]+back_time[i]
print(maxTime)