백준 1238 파티

과정

• 다익스트라
• 집 -> 파티장, 파티장 -> 집 의 거리를 최단 거리를 학생 별로 구하고, 그 중 최대를 출력한다.
• 단방향으로 주어지는 점에 주의한다.
• 다익스트라를 구현하고, 파티장에서 집까지 거리 + 각 학생이 파티장에 오는 거리 의 최단 거리를 구한다.
• ans과 비교해서 크면 ans 업데이트 한다.

시행착오

• 모든 학생에 대해서 X까지의 거리를 구해야해서 플루이드 워셜을 했더니 시간 초과가 나왔다.
  • 플루이드 워셜의 시간복잡도는 N^3, 다익스트라는 ElogV이다.
  • 모든 경우의 수가 필요하지 않으면 일반적으로 다익스트라를 사용하는게 좋은 듯 하다.

import sys
input = sys.stdin.readline

import heapq

N, M, X = map(int, input().split())
INF = 1e9

graph = [[] for _ in range(N)] # 연결된 노드 정보 저장 (노드, 가중치)
for _ in range(M):
    s, e, T = map(int, input().split())
    graph[s-1].append((e-1, T))

def dijkstra(start):
    # initialization
    distance = [INF] * N
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if dist > distance[now]: # 이미 처리된 곳임
            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

ans = 0
from_end = dijkstra(X-1)
for i in range(N):
    total_dist = dijkstra(i)[X-1] + from_end[i]
    if ans < total_dist:
        ans = total_dist

print(ans)```