[백준 알고리즘] 1283. 파티 _ 파이썬

 

SWEA 1795 인수의 생일파티와 유사한 문제이다.

 

각자의 집 ->  파티하는 집  -> 각자의 집으로 가는 최단경로를 구해야 한다.

 

 

한 점에서 여러 점 갈 때는 다익스트라를 한 번 돌리면 되지만, 여러 점에서 한 점으로 갈 때는 각 시작점마다 다익스트라를 돌려야 한다. 

 

불필요하게 다익스트라로 구하는 것을 방지하고자

아예 경로를 여러 점에서 한점으로 가는 것 -> 한 점에서 여러 점을 방문하도록 그래프를 추가했다.

 

그래서 가는 방향 경로 GO, 오는 방향 경로 COME을 나눠서 다익스트라르 2번 돌려 구했다.

 

 

 

from heapq import heappush, heappop
INF = 0xffffffffffffffffff

# 어떤 시작점에서 모든 정점까지의 최단거리
def dijkstra(start, graph):
    visited = [0] * (N+1)
    D = [INF] * (N+1)
    D[start] = 0
    Q = [(0, start)]
    while Q:
        d, u = heappop(Q)
        if visited[u]: continue
        visited[u] = 1

        for v, t in graph[u]:
            if not visited[v] and D[v] > d + t:
                D[v] = d + t
                heappush(Q, (D[v], v))
    return D[1:]


N, M, X = map(int, input().split())
# N명의 학생, M개의 도로, X 파티하는 장소
go = [[] for _ in range(N+1)]
come = [[] for _ in range(N+1)]

for i in range(M):
    s, e, t = map(int, input().split())
    # 가는 길, 오는 길 경로 그래프 나누기
    go[s].append((e, t))
    come[e].append((s, t))

print(max( a + b for a, b in zip(dijkstra(X, go), dijkstra(X, come))))