[백준] 1238번 - 파티 (파이썬)

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

# 파티
import sys
import heapq
input = sys.stdin.readline
MAX = sys.maxsize
N, M, X = map(int, input().split())
arr = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, cost = map(int, input().split())
    arr[a].append((cost, b))

come = [MAX] * (N+1)
go = [MAX] * (N+1)


def go_dijkstra(x):
    q = []
    heapq.heappush(q, (0, x))
    go[x] = 0
    while q:
        cost, node = heapq.heappop(q)
        for ncost, nnode in arr[node]:
            if go[nnode] > ncost + go[node]:
                go[nnode] = ncost + go[node]
                heapq.heappush(q, (ncost, nnode))


def come_dijkstra(x):
    temp = [MAX] * (N+1)
    q = []
    heapq.heappush(q, (0, x))
    temp[x] = 0
    while q:
        cost, node = heapq.heappop(q)
        for ncost, nnode in arr[node]:
            if temp[nnode] > ncost + temp[node]:
                temp[nnode] = ncost + temp[node]
                heapq.heappush(q, (ncost, nnode))
    return temp[X]


go_dijkstra(X)
for i in range(1, N+1):
    come[i] = come_dijkstra(i)

result = [0] * (N+1)
for i in range(1, N+1):
    result[i] = come[i]+go[i]
print(max(result))

 

최단거리, 다익스트라

1. 목표지점(X)에서 각 노드로 가는 최단거리를 go리스트에 저장 (go_dijkstra 함수)

2. 각 노드에서 목표지점(X)로 오는 최단거리를 come리스트에 저장 (come_dijkstra 함수를 노드수만큼 실행해서)

3. go와 come의 합을 result에 저장하고 max(result)출력

 

 

방향 그래프의 최단거리이다. 그래서 다익스트라 알고리즘으로 올 때 와 갈 때의 경우 두가지로 나눠서 계산했다.