[ALGORITHM] BOJ 1238. 파티

---

ALGORITHM Übung - 백준

• 알고리즘 문제 풀이를 통한 코딩 테스트 연습

---

문제

• 🔗 문제 링크

코드

import sys
import heapq

def dijkstra(start):
    
    dists = [float("inf")] * (n+1)
    dists[start] = 0
    
    q = []
    heapq.heappush(q, (0, start))
    
    while q:
        dist, now = heapq.heappop(q)
        
        if dists[now] < dist:
            continue
        
        for node_index, node_cost in graph[now]:
            cost = dist + node_cost
            
            if cost < dists[node_index]:
                dists[node_index] = cost
                heapq.heappush(q, (cost, node_index))
                
    return dists


if __name__ == "__main__":
    
    n, m, x = map(int, sys.stdin.readline().split())

    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b,c = map(int, sys.stdin.readline().split())
        graph[a].append((b,c))
    
    node2 = dijkstra(x)
    max_length = 0
    for i in range(1, n+1):
        if i != x:
            max_length = max(max_length, dijkstra(i)[x] + node2[i])
    
    print(max_length)