[백준 1238] 파티 (Python 풀이, Gold III)

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

1238번: 파티

 

 dijkstra로 푸는 문제다. 일단 잘 구현된 dijkstra 함수 하나를 갖고 오자. 숙련자는 7분 만에 짤 수 있다.

 어떤 그래프 G의 한 노드 v에 대해서 v로부터 모든 노드로 가는 최단경로의 거리를 각각 구해주는 것은 쉽다. 그러나 모든 노드에 대해서 모든 노드로부터 v로 가는 최단경로의 거리를 각각 구해주는 것은 약간의 생각이 더 필요하다.

 간선의 방향을 바꿔준다는 아이디어를 떠올리면, 모든 노드 -> v로 가는 최단경로를 구하는 문제가 v -> 모든 노드로 가는 최단경로 문제로 바뀐다는 것을 바로 알 수 있다.

 따라서 유향그래프 G를 만든 다음 G의 모든 간선의 방향을 뒤집어준 그래프 H를 만들고, G와 H에서 dijkstra를 각각 돌리면 된다.

import sys
from queue import PriorityQueue
from collections import namedtuple

input = sys.stdin.readline
Edge = namedtuple('Edge', ['next', 'value'])
Vertex = namedtuple('Vertex', ['value', 'id'])


def dijk(grid: list[list[Edge]], source: int) -> list[int]:
    n = len(grid)
    dists = [10 ** 10 for _ in range(n)]
    q = PriorityQueue()

    q.put(item=Vertex(value=0, id=source))
    dists[source] = 0

    while not q.empty():
        v_val, v_now = q.get()
        for v_next, e_val in grid[v_now]:
            if dists[v_next] > v_val + e_val:
                dists[v_next] = v_val + e_val
                q.put(item=Vertex(value=v_val + e_val, id=v_next))

    return dists


n, m, x = map(int, input().split())
x -= 1

grid: list[list[Edge]] = [[] for _ in range(n)]
grid_rev: list[list[Edge]] = [[] for _ in range(n)]
for _ in range(m):
    s, e, v = map(int, input().split())
    s -= 1
    e -= 1
    grid[s].append(Edge(next=e, value=v))
    grid_rev[e].append(Edge(next=s, value=v))

d1 = dijk(grid, x)
d2 = dijk(grid_rev, x)
ret = 0
for i in range(n):
    ret = max(ret, d1[i] + d2[i])

print(ret)