[백준] 1238번 파티

💡문제접근

• 모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
• N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있으므로 각각의 집에서 출발해서 X에 도달한 후 X에서 출발해서 각각의 집으로 돌아올 때 가장 오래 걸리는 학생의 시간을 출력하면 해결할 수 있다.

💡코드(메모리 : 34348KB, 시간 : 2016ms)

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

N, M, X = map(int, input().strip().split())
graph = [[] for _ in range(N+1)]
distance = [INF] * (N+1)
for _ in range(M):
    a, b, T = map(int, input().strip().split())
    graph[a].append([b, T])

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance = [INF] * (N + 1)
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return distance

result = 0
for i in range(1, N+1):
    start = dijkstra(i)
    end = dijkstra(X)
    result = max(result, start[X] + end[i])
print(result)

💡소요시간 : 27m