[python] 백준 1238 파티

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

1238번: 파티

 

문제 해결

• 다익스트라 문제
• for문을 통해 1~n까지 한 점 i에서 x까지 가는데 최소 시간를 구하고 x에서 i까지 가는데 최소 시간를 구해서 더하면 왕복 최소 시간이 나온다.
• 리스트를 통해 최댓값을 구하면 된다.

 

CODE

 

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

n, m, x = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    start, end, time = map(int, input().split())
    graph[start].append((time, end))

def dijkstra(start):
    heap = []
    record = [INF]*(n+1)
    heapq.heappush(heap, (0,start))
    record[start] = 0
    record[0] = 0
    
    while heap:
        time, now = heapq.heappop(heap)
        if record[now] < time: continue
        for next_time, next_index in graph[now]:
            t = time + next_time
            if record[next_index] > t:
                record[next_index] = t
                heapq.heappush(heap,(t,next_index))
    return record

ans = 0
for i in range(1,n+1):
    go = dijkstra(i)
    back = dijkstra(x)
    ans = max(ans, go[x]+back[i])
print(ans)