[백준 - Python] 1238. 파티

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

 

코드

# 다익스트라 두 번 쓰는 풀이
import heapq
INF = int(1e9)

def dijkstra(start):
    distance = [INF] * (N+1)
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    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


N, M, X = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    s, e, t = map(int, input().split())
    graph[s].append([e, t])

ans = dijkstra(X)
ans[0] = 0
for i in range(1, N+1):
    if i != X:
        res = dijkstra(i)
        ans[i] += res[X]

print(max(ans))

 

접근 방법

- 플로이드 워셜로 풀면 되겠다고 생각했지만 시간 초과

- N이 최대값인 경우 10억번의 연산이 필요하게 되고, 시간 초과 발생

- 다익스트라를 2번 사용하는 풀이 참고

 

배운 점

- 플로이드 워셜을 복습할 수 있었다

- 다익스트라 시간 복잡도는 O((N+M) log N)이다

- 다익스트라를 한 번 사용해서 X에서 모든 노드로 가는 최단 경로를 구하고, 모든 노드에서 X로 가는 최단 경로를 구한 후에 더해서 최대 소요시간 구할 수 있다

- 다익스트라 함수를 재사용하기 위해 최단거리 테이블을 반환하는 형태로 함수를 구성할 수 있다