[백준] 1238번: 파티 - 다익스트라에서 출발점과 도착점을 뒤집으면

문제

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

풀이

import sys

sys.stdin = open("data.txt", "r")

import heapq

INF = int(1e9)
N, M, X = map(int, sys.stdin.readline().rstrip().split(" "))
graph = {start: {} for start in range(1, N + 1)}
reverse_graph = {start: {} for start in range(1, N + 1)}
for _ in range(M):
    start, end, weight = map(int, sys.stdin.readline().rstrip().split(" "))
    graph[start][end] = weight
    reverse_graph[end][start] = weight


def dijkstra(start, graph):
    distances = {end: INF for end in range(1, N + 1)}
    distances[start] = 0
    heap = [(0, start)]

    while heap:
        cur_distance, cur = heapq.heappop(heap)
        if distances[cur] < cur_distance:
            continue

        for neighbor, weight in graph[cur].items():
            next_distance = cur_distance + weight
            if next_distance < distances[neighbor]:
                distances[neighbor] = next_distance
                heapq.heappush(heap, (next_distance, neighbor))

    return distances


def solution():
    answer = -1
    goHome = dijkstra(X, graph)
    goParty = dijkstra(X, reverse_graph)

    for start in range(1, N + 1):
        answer = max(answer, goHome[start] + goParty[start])
    print(answer)


solution()

회고

이 문제는 다익스트라를 2번만 돌려서 풀 수 있다.

처음에 생각할 때는 도착점에서 출발점으로 가는 모든 경로 길이를 구해 재활용하고
출발점들을 순회하면서에서 도착점으로 가는 최단 경로를 구한 뒤 합해서 최대 경로를 구할려고 했다.

이렇게 하면 마을 수 + 1 번 다익스트라 함수를 호출해야한다.

최대 마을 수는 V = 1000이고 최대 정점의 수는 E = 10000 이므로
시간 복잡도는 (1000+1) * O(10000log1000) = 1001 * 30000 = 30,030,000 으로
시간 초과가 난다.

다익스트라 알고리즘은
임의의 정점(X)에서 각 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다.

만약 그래프를 생성할때 출발점과 도착점을 변경한 후 다익스트라 알고리즘을 실행하는 행위는
모든 정점에서 임의의 정점(X)으로 가는 최단 경로를 모두 구하는 로직이 된다.

유용할 것 같다.