[백준][Python] 1238 파티 : 역방향 그래프로 돌아오는 길을 찾자

처음 풀이는 다음과 같다. 모든 노드에 갔다가 돌아오는 각 합중 max값을 찾는 풀이

그리고 다른 분들의 풀이를 본 결과 역방향 그래프를 그리는 것이 반대로 도착지점에서 현지점까지 오는 거리를 측정할 수 있음을 깨달았다.

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

def dijkstra(start):
    heap = []
    visited = {i: float('inf') for i in range(1, N + 1)}
    visited[start] = 0
    heappush(heap, (0, start))
    while heap:
        time, cur_node = heappop(heap)
        if visited[cur_node] < time:
            continue
        for next_node, next_time in graph[cur_node]:
            if visited[next_node] > time + next_time:
                visited[next_node] = time + next_time
                heappush(heap, (visited[next_node], next_node))
    return visited
N, M, X = map(int, input().split())
graph = {i: [] for i in range(1, N + 1)}
for __ in range(M):
    s, e, t = map(int, input().split())
    graph[s].append((e, t))

max_dist = 0
dist_X = dijkstra(X)
for i in range(1, N + 1):
    if i == X: continue
    each = dijkstra(i)
    max_dist = max(max_dist, dist_X[i] + each[X])
print(max_dist)

 

다른분의 풀이(역방향 그래프 이용)

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
n, m, x = map(int, input().split())
inf = 100000000
s = [[] for i in range(n + 1)]
dp = [inf] * (n + 1)
s_r = [[] for i in range(n + 1)]
dp_r = [inf] * (n + 1)
def dijkstra(start, dp, s):
    heap = []
    dp[start] = 0
    heappush(heap, [0, start])
    while heap:
        w, n = heappop(heap)
        if dp[n] < w:
            continue
        for n_n, wei in s[n]:
            n_w = wei + w
            if n_w < dp[n_n]:
                dp[n_n] = n_w
                heappush(heap, [n_w, n_n])
for i in range(m):
    a, b, t = map(int, input().split())
    s[a].append([b, t])
    s_r[b].append([a, t])
dijkstra(x, dp, s)
dijkstra(x, dp_r, s_r)
max_ = 0
for i in range(1, n + 1):
    max_ = max(max_, dp[i] + dp_r[i])
print(max_)

정방향을 통해 X -> 특정노드

역방향을 통해 X -> 특정노드의 역 방향 즉 특정노드 -> X까지 오는 경로를 역으로 타고 들어간다.