파티 (1238번) - 백준 (BOJ)

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

1238번: 파티

 

 

백준 - 파티 (Silver Cow Party) (1238번)

 

난이도 : Gold 3

알고리즘 : Dijkstra (다익스트라)

Time Complexity : O( E * logV )

 

 

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


def dijkstra(b, d):
    pq = [(0, X)]
    while pq:
        t, v = heappop(pq)
        if d[v] < t:
            continue
        for tt, vv in b[v]:
            if d[vv] <= t+tt:
                continue
            d[vv] = t+tt
            heappush(pq, (t+tt, vv))


if __name__ == '__main__':
    INF = sys.maxsize
    N, M, X = map(int, input().split())
    ib = [[] for _ in range(N+1)]
    ob = [[] for _ in range(N+1)]
    iid = [INF] * (N+1)
    ood = [INF] * (N+1)
    iid[X] = ood[X] = 0
    for _ in range(M):
        a, b, t = map(int, input().split())
        ib[b].append((t, a))
        ob[a].append((t, b))
    dijkstra(ib, iid)
    dijkstra(ob, ood)
    print(max(sum(tup) for tup in zip(iid[1:], ood[1:])))

 

 

2개의 그래프를 분리해서 만들어야 한다.

ib[m] : 노드 m으로 들어오는 방향의 간선들을 저장하는 리스트
ob[m] : 노드 m에서 나가는 방향의 간선들을 저장하는 리스트

 

 

각 시점에서, 노드 X로부터 노드 m까지 최소 거리를 저장하는 리스트도 따로 만든다.

iid[m] : m에서 X까지 최소거리 저장하는 리스트
ood[m] : X에서 m까지 최소거리 저장하는 리스트

 

 

위와 같이 리스트들을 구성한 다음,

다익스트라(dijkstra) 알고리즘을

들어오는 방향과 나가는 방향 각각 한 번씩

총 두 번 실행한다.

 

 

이후, 거리를 저장한 iid와 ood의 값을 각 노드 별로 더하면서

최대값을 출력하면 된다.