[Python] 백준 1238번 : 파티

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

1238번: 파티

---

💡 문제 풀이

그래프 이론 중 다익스트라 알고리즘 문제이다.

 

기본적인 다익스트라 알고리즘과 형태가 비슷하지만 주의할 점이 있다.

바로, 원하는 값이 특정 노드에서 목적지로의 거리 + 목적지부터로의 거리라는 점이다.

구현한 다익스트라 알고리즘은 출발지로부터 모든 정점에 대해서 최단 거리를 구해준다.

따라서 최단 거리를 저장하는 배열을 2개를 구현해서 최대 거리를 찾아준다.

✔️ 느낀 점

사실 코드를 다르게 구현할 수 있었는데 처음에 문제를 제대로 안 읽고 무지성으로 시작점부터 계산하는 

다익스트라 알고리즘을 구현해버렸다. 그래서 메모리랑 시간 확인하고 대충 때려넣었다 ^^

💻 코드

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

N, M, X = map(int, input().split())
graph = [[] for _ in range(N+1)]

for _ in range(1, M+1):
    s, e, c = map(int, input().split())
    graph[s].append([c,e])

to_dest, from_dest = [INF] * (N+1), [INF] * (N+1)
max_ = 0
queue = []

def dijkstra(start, dist):
    dist[start] = 0
    heapq.heappush(queue, [0, start])
    
    while queue:
        current_cost, current_node = heapq.heappop(queue)
        
        if dist[current_node] < current_cost: continue
        
        for new_cost, new_node in graph[current_node]:
            distance = new_cost + current_cost
            if distance < dist[new_node]:
                dist[new_node] = distance
                heapq.heappush(queue, [distance, new_node])
           
dijkstra(X, from_dest)
for i in range(1, N+1):
    dijkstra(i, to_dest)
    max_ = max(max_ ,to_dest[X] + from_dest[i])
    to_dest = [INF] * (N+1)
    
print(max_)