백준 1238 파티 (파이썬)

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

1238번: 파티

다익스트라로 최단 시간에 해당하는 경로를 구한다

 

1. 끝점 까지 가는 최단 시간 경로를 구한다

2. 다시 시작점으로 돌아오는 최단 시간 경로를 구한다

3. 1번과 2번값을 더하여 저장한 후 그 중에서 최대값을 출력

import sys, heapq

INF = sys.maxsize
input = sys.stdin.readline

def dij(x):
    d = [INF]*n
    heapq.heappush(heap, [0, x])
    d[x] = 0
    while heap:
        w, x = heapq.heappop(heap)
        for nw, nx in a[x]:
            nw += w
            if nw < d[nx]:
                d[nx] = nw
                heapq.heappush(heap, [nw, nx])
    return d

n, m, t = map(int, input().split())
a = [[]*n for _ in range(n)]
heap = []

for i in range(m):
    x, y, w = map(int, input().split())
    a[x-1].append([w, y-1])

ans = [0]*n
for i in range(n):
    d = dij(i)
    ans[i] += d[t-1]
    d = dij(t-1)
    ans[i] += d[i]
print(max(ans))