[백준] 1238 파티

문제

• N개 숫자로 구분된 마을에 학생이 한 명씩 살고 있고, 마을 사이에는 M개의 단방향 도로가 존재한다.
  • 1 <= N <= 1000
  • 1 <= M <= 10,000
  • 각 도로를 지나는데 $T_i$의 시간이 소비된다.
• N명의 학생이 각자 최단 시간으로 X번 마을에서 모일 때, 왕복 시간이 가장 긴 학생 구하기

 

풀이

• N개 마을 각각에 대해서 i 번 마을 -> X번 마을 가는 최단 경로 구하고, 최댓값 찾기
  
  • 크루스칼로 각 노드에서 X 노드까지의 최단 경로 (가는 길) + X 노드에서 각 노드 최단 경로 (오늘 길)
• 시간 복잡도 : $O(NMlogN)$ 
• 플로드 와샬로 하면 $O(N^3)$ 이므로 시간 초과 나온다.

 

import sys
import heapq
INF = sys.maxsize

N, M, X = map(int, input().split())
graph = [[] for _ in range(N+1)]      # 그래프 입력받기
for _ in range(M):  
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

# 다익스트라 함수
def dijkstra(start, distance):
    q = []
    heapq.heappush(q, (0, start))   # 시작 노드 추가
    distance[start] = 0             # 시작 노드 거리 0 초기화

    while q:
        dist, now = heapq.heappop(q)    # 현재 거리, 노드

        if distance[now] < dist :       # 이미 최단거리면 무시
            continue

        for i in graph[now]:            # 연결된 노드들 중
            cost = dist + i[1]          

            if cost < distance[i[0]]:   # 현재 노드 거쳐서 최단인 경우 업데이트
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return distance

# X 노드에서 돌아가는 최단 경로 구하기
back = [INF] * (N+1)
back = dijkstra(X, back)

# 1 ~ N번 노드의 왕복 거리 구하기
answer = 0
for i in range(1, N+1):
    distance = [INF] * (N+1)
    answer = max(answer, dijkstra(i, distance)[X] + back[i])
print(answer)

 

References

• 백준 1238번
• 2023.04.26 오늘의 문제