[백준1238] / 파티 - 다익스트라

 

백준1238

 

푼 날짜 : 2024.11.11

푼 문제 : [1238] / 파티

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근 방식 :

각 위치에서 X까지 걸리는 시간 + X에서 각 위치까지 걸리는 시간을 계산하여 가장 오래걸리는 시간을 출력하도록 했다.

 

 

코드 : 

import sys
import heapq

N, M, X = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    start, end, time = map(int, sys.stdin.readline().split())
    graph[start].append((end, time))

def dijkstra(start):
    
    heap = [(start, 0)]
    dist = [float("INF") for _ in range(N+1)]
    dist[start] = 0

    while heap:
        n_node, n_time = heapq.heappop(heap)

        if dist[n_node] < n_time: continue

        for  node, time in graph[n_node]:
            all_time = n_time + time

            if dist[node] > all_time:
                dist[node] = all_time
                heapq.heappush(heap, (node, all_time))
    
    return dist

# 가는 길, 오는 길 합산을 위한 배열
check = [0 for _ in range(N+1)]
# 각 위치에서 X로의 이동시간
for i in range(1, N+1): check[i] = dijkstra(i)[X]
# X에서 각 위치로의 이동시간
lst = dijkstra(X)
# 시간 합산
for i in range(1, N+1): check[i] += lst[i]
# 최댓값 출력
print(max(check[1:]))

 

 

 

헤헤 다익스트라도 이제 잘 할 수 있어!!!