[BAEKJOON]1238 파티 - Python

문제 요약

• 알고리즘 분류: 다익스트라
• 난이도: Gold5
• 문제내용:
  • 각 노드에서 X까지 시작점 부터 도착점 왕복하는데 걸리는 최대 시간을 구해라

• 사이트: https://www.acmicpc.net/problem/1238

1238번: 파티

문제풀이

   이번에는 문제 유형은 그래프 탐색중에 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘 기본적인것을 묻기 때문에 자세한 설명은 여기서 참조하면된다. 풀이에 대한 설명은 각 노드에서 X까지 출발점 부터 도착점 까지 왕복 하는데 걸리는 시간을 다익스트라 알고리즘을 출발점 → 도착점, 도착점 → 출발점을 구해서 더하기만 하면되기 때문에 다익스트라 알고리즘알면 풀수 있기때문에 따로 설명은 하지 않겠다. 

Code

Python

import sys, heapq
input = sys.stdin.readline
INF = 1e9

def dijkstra(start, end):
    distances = [INF] * (N + 1)
    distances[start] = 0
    queue = [(0, start)]

    while queue:
        now_distance, now_node = heapq.heappop(queue)
        if now_distance > distances[now_node]: continue
        for node, weight in grape[now_node]:
            distance = now_distance + weight

            if distances[node] > distance:
                distances[node] = distance
                heapq.heappush(queue, (distance, node))

    return distances[end]


N, M , X = map(int, input().split())    
grape = {i: [] for i in range(1, N + 1)}

for _ in range(M):
    a, b, T = map(int, input().split())
    grape[a].append([b, T])

max_distance = 0
for i in range(1, N + 1):
    max_distance = max(dijkstra(X, i) + dijkstra(i, X), max_distance)

print(max_distance)