문제

[백준] 파티 (Gold 3)

요약

N명의 학생이 X번 마을에 모여서 파티를 한다. M개의 도로가 있고 i번째 길을 지나는 데 T(i)의 시간을 소비한다. 각각의 학생들은 X번 마을에 최단 거리로 갔다가 다시 그들의 마을로 최단거리로 돌아와야 한다. 도로는 단방향이다. 오고 가는 데 가장 많은 시간을 소비하는 학생을 구하라.

분류

  • 다익스트라

풀이

1. 내 풀이 (그래프 1개, 다익스트라 N번)

N개의 학생에 대해 N번의 다익스트라 알고리즘을 실행해준다. 실행 시간 1500ms

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

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

for _ in range(m):
    a, b, t = map(int, input().split())
    graph[a - 1].append((b - 1, t))

arr = []

for start in range(n):  # 각각의 학생에 대하여
    d = [sys.maxsize] * n
    d[start] = 0

    queue = [(0, start)]

    while queue:
        w, index = heappop(queue)

        if w > d[index]:
            continue

        for node, weight in graph[index]:
            if d[index] + weight < d[node]:
                d[node] = d[index] + weight
                heappush(queue, (d[node], node))

    arr.append(d)

ans = -1
for i, d in enumerate(arr):
    ans = max(ans, d[x - 1] + arr[x - 1][i])

print(ans)

2. 더 나은 풀이 (그래프 2개, 다익스트라 2번)

원래 그래프와 arc의 방향을 뒤집은 그래프로 두 번의 다익스트라를 진행한다. 실행 시간은 약 50ms

링크