파티

접근

문제에 대해서 간략히 설명하자면, '한 노드에서 모든 노드까지의 최단거리(일반적인 다익스트라) + 모든 노드에서 특정 노드까지의 최단거리'를 구하는 문제다.

처음에는 플로이드 워셜을 떠올렸다. 그런데 정점 수가 1000개이고 시간제한이 1초인 것을 보아 시간초과가 날 것이 분명했다.

다시 생각해보니 모든 노드에서 한 노드까지의 거리를 구하는 것이나 한 노드에서 모든 노드까지의 거리를 구하는 것이나 간선의 방향만 다르다는 것을 깨달았다. 그래서 다익스트라 알고리즘을 두 번 이용하여 해결하면 되겠다고 생각했다.

구현

import heapq
n, m, k = map(int, input().split())
INF = 1e9

graph = [[] for _ in range(n+1)]
graph2 = [[] for _ in range(n+1)]

distance = [INF] * (n+1)
distance2 = [INF] * (n+1)

for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph2[v].append((u, w))


def dijkstra(start, g):
    if g == 1:
        g = graph
        d = distance
    else:
        g = graph2
        d = distance2
    q = []
    heapq.heappush(q, (0, start))
    d[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if d[now] < dist:
            continue 

        for i in g[now]: 
            if dist+i[1] < d[i[0]]: 
                d[i[0]] = dist+i[1]   
                heapq.heappush(q, (dist+i[1], i[0]))

dijkstra(k, 1)
dijkstra(k, 2)

res = 0
for i in range(1, n+1):
    res = max(res, distance[i]+distance2[i])

print(res)

다익스트라 알고리즘

heap 사용 없이 구현하는 방법 (간선 수가 많다면 이게 더 빠를 수 있음을 고려해야 함)