[Baekjoon/python] 파티 #1238

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

1238번: 파티

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

코드

• 다익스트라 알고리즘 적용
• 각 출발지에서 모든 도착지까지의 걸린 시간을 구함
• "출발지 -> 도착지 -> 출발지" 에서 "도착지 -> 출발지"를 먼저 구해둔 후 "출발지 -> 도착지" 시간과 더함

N, M, X = map(int, input().split())
graph = defaultdict(list)
for _ in range(M):
    src, dst, time = map(int, input().split())
    graph[src - 1].append((time, dst - 1))

def dijkstra(src):
    heap = [(0, src)]
    min_time = [float('inf')] * N
    min_time[src] = 0
    while heap:
        cur_time, cur_node = heapq.heappop(heap)
        for nxt_time, nxt_src in graph[cur_node]:
            if nxt_time + cur_time < min_time[nxt_src]:
                min_time[nxt_src] = nxt_time + cur_time
                heapq.heappush(heap, (cur_time + nxt_time, nxt_src))
    return min_time

answer = 0

# 도착지 -> 출발지
x_to_n_time = dijkstra(X - 1)

# 출발지 -> 도착지
for i in range(N):
    if i != X - 1:
        i_to_x_time = dijkstra(i)
        answer = max(answer, i_to_x_time[X - 1] + x_to_n_time[i])

print(answer)