[백준] 1238번 파티 (파이썬)

난이도 : GOLD III

문제링크 : https://www.acmicpc.net/problem/1238

문제해결 아이디어

• 다익스트라 기본문제
• 단방향이기 때문에 graph[시작점].append(끝점) 을 해주고
• heap을 통해 최소경로를 찾는다.

소스코드

import sys
import heapq

input = sys.stdin.readline

n,m,x = map(int, input().split())

graph = [[] for _ in range(n+1)]

for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a].append((b,c))

ans = []
INF = int(1e9)
def dijk(start,end):
    if end == start:
        return 0
    h = []
    heapq.heappush(h, (0, start))
    distance = [INF] * (n+1)
    distance[start] = 0
    while h:
        dist, now = heapq.heappop(h)

        if distance[now] < dist:
            continue

        for node,c in graph[now]:
            cost = c + dist
            if cost < distance[node]:
                heapq.heappush(h,(cost,node))
                distance[node] = cost

    return distance[end]

for i in range(1,n+1):
    cnt = 0
    cnt += dijk(i,x)
    cnt += dijk(x,i)
    ans.append(cnt)

print(max(ans))