[파이썬] 백준 1238 : 파티 (골드3)

[파이썬] 백준 1238 : 파티 (골드3)

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

---

풀이

방향성 생각

• 모든 노드에 대해서 다익스트라 돌려서 걸리는 시간 얻기.

 

---

전체코드

import heapq as hq
import sys

input = lambda : sys.stdin.readline().rstrip()
INF = float('inf')

N,M,X = map(int,input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a,b,cost = map(int,input().split())
    G[a].append((b,cost))

def di(x):
    V = [INF]*(N+1)
    V[x] = 0
    heap = [(0,x)]

    while heap:
        t,x = hq.heappop(heap)

        if t>V[x]:
            continue

        for nx,cost in G[x]:
            nt = t+cost
            if nt < V[nx]:
                hq.heappush(heap,(nt,nx))
                V[nx] = nt
    return V

dist = [di(i) for i in range(N+1)]
answer = [dist[i][X]+dist[X][i] for i in range(1,N+1)]
print(max(answer))

---

코멘트

• 다익기본