Baekjoon 1238. 파티 / Python

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

알고리즘 설명

문제 설명

단방향 그래프에서 최단경로를 찾는 문제
최단 경로의 값을 모두 구하고 그 중에 최댓값을 찾는다.

코드 설명

사람 별로 파티장까지 갔다가 돌아오는 길의 최단경로를 찾는다.
최단경로의 경로길이들의 최댓값을 갱신한다.

import sys
from heapq import heappop, heappush

input = sys.stdin.readline

inf = 1e10

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

# 최단경로구하기
def sol(start, end):
    dp = [inf for _ in range(n + 1)]
    dp[start] = 0
    q = []
    heappush(q, (0, start))
    while q:
        time, now = heappop(q)
        if dp[now] < time:
            continue
        for tmp, next in arr[now]:
            if tmp + time < dp[next]:
                dp[next] = tmp + time
                heappush(q, (tmp + time, next))
    return dp[end]

# 도로 정보 
for _ in range(m):
    s, e, t = map(int, input().split())
    arr[s].append([t, e])

res = 0

# 모든 학생에 대해 계산
for i in range(1, n + 1):
    res = max(res, sol(i, x) + sol(x, i))

print(res)