[백준] 1238번 파티 - 파이썬

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

1238번: 파티

이 문제는 다익스트라를 이용한 최단 경로 문제이다.

 

이문제의 특성이라면 최단 경로로 갔다가? 다시 돌아와야한다

이러한 점만 고려하면 기본적인 다익스트라 알고리즘에 문제의 조건에만 맞게 해주면 해결 가능하다.

import sys
import heapq

n, m, x = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n + 1)]
INF = int(1e9)


for _ in range(m):
    a, b, t = map(int, sys.stdin.readline().split())
    graph[a].append((b, t))


def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance = [INF] * (n + 1)
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in graph[now]:
            b, t = i
            cost = dist + t
            if cost < distance[b]:
                distance[b] = cost
                heapq.heappush(q, (cost, b))
    return distance

distance2 = dijkstra(x)
answer = 0

for i in range(1, n + 1):
    # i에서 출발한 최단 경로들
    distance1 = dijkstra(i)
    answer = max(answer, distance1[x] + distance2[i])
print(answer)