[SWEA 1795] 인수의 생일파티

 

 

다익스트라로 풀었음!

 

 

각자의 집에서 -> X번 집(생일파티집) => 각자의 집

 

 

X번 -> 각자의 집은 다익스트라 한 번 돌리면 되지만,

 

각자의 집에서 X번집의 최단거리들을 구하려면 여러번 돌아야 한다.

 

그래서 그래프를 만들때 각자의 집 -> X번 집을 쉽게 구하기 위해서 X 번집을 기준으로 두고, 각자의 집으로 가는 (반대방향) 으로 그래프를 만들어 다익스트를 2번만 돌리면 되도록 했다!

 

 

from collections import deque
INF = int(1e9)

def dijkstra(start, graph):
    D = [INF] * (n + 1)
    D[start] = 0
    Q = deque()
    Q.append(start)
    while Q:
        node = Q.popleft()
        for n_node, w in graph[node]:
            d = D[node] + w
            if d < D[n_node]:
                D[n_node] = d
                Q.append(n_node)
    return D[1:]


for tc in range(1, int(input()) + 1):
    n, m, x = map(int, input().split())
    go, come = [[] for _ in range(n + 1)], [[] for _ in range(n + 1)]
    for _ in range(m):
        s, e, w = map(int, input().split())
        come[s].append((e, w)) # 집에 돌아올 때
        go[e].append((s, w)) # 생일 파티 갈때

    ans = max(a + b for a, b in zip(dijkstra(x, go), dijkstra(x, come)))
    print('#{} {}'.format(tc, ans))