[백준 1238번] 파티 문제 풀이

 

 

<문제>

 

 

 

 

 

 

<입출력>

 

 

 

 

 

<풀이>

먼저 간단한 다익스트라 구조를 이용하여 가는 거리와 오는 거리를 구해 최댓값을 구했는데, 입출력은 동일하나 시간 초과가 나왔다.

그래서, 힙을 이용하여 개선된 다익스트라 알고리즘을 사용하였더니 해결되었다. 

 

 

 

 

 

<코드>

import sys
import heapq

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

# 노드의 개수, 간선의 개수 입력 받기
n, m, x = map(int, input().split())
# 각 노드에 연결 되어 있는 노드에 대한 정보를 담는 리스트 만들기
graph = [[] for i in range(n +1)]

# 모든 간선 정보를 입력 받기
for _ in range(m):
    a, b, c = map(int ,input().split())   # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b, c))


def dijkstra(start):
    q = []
    distance = [INF] * (n + 1)

    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for node_index, node_cost in graph[now]:
            cost = dist + node_cost

            if distance[node_index] > cost:
                distance[node_index] = cost
                heapq.heappush(q, (cost, node_index))

    return distance


result = 0
for i in range(1, n + 1):
    go = dijkstra(i)
    back = dijkstra(x)
    result = max(result, go[x] + back[i])

print(result)