[백준] 9466 텀프로젝트 : 다익스트라로 왕복하기

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

9466번: 텀 프로젝트

각 노드들에서 x로 갈때 다익스트라 최단경로 알고리즘을 이용해 최단거리를 구하면 노드 i에서 모든 노드까지의 최단 거리 결과를 알 수 있다. 이 결과값을 나는 최단 거리를 저장하는 리스트 dist라고 두었다. dist[x]값이 바로 학생 i가 파티 주최지 x 노드까지 '가는' 데에 소요되는 최단경로 cost이다. 

문제는 왕복을 해야 한다는 것인데, 원래는 구해놓은 최단거리에 2배 곱해주면 되지 않나라고 생각했으나, 문제에서 그래프는 양방향이 아니라 일방향 간선들로 이루어져있으므로 다시 우리는 다익스트라를 이용하여 x에서 노드 i까지 가는 거리를 구해야 한다. 

그리고 ( 가는데 걸린 최단시간 + 돌아오는데 걸린 최단시간 )의 합을 모두 비교해준 후 합이 가장 큰 노드(학생)을 구하면 된다 ! 

다익스트라만 떠올리면 바로 어렵지 않게 풀 수 있는 문제이다 !

# 9466 텀프로젝트
import heapq
INF = int(1e9)
n, m, x = map(int, input().split()) # N M X
graph = [[] for _ in range(n+1)]


for i in range(m):
    s, e, t = map(int, input().split())
    graph[s].append((e, t))

def dijkstra(start):
    dist = [INF] * (n+1)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        d, now = heapq.heappop(q)
        if dist[now] < d:
            continue
        for next, cost in graph[now]:
            if dist[next] > dist[now] + cost:
                dist[next] = dist[now] + cost
                heapq.heappush(q, (dist[next], next))
    return dist 



result = 0
for i in range(1, n+1):
    first = dijkstra(i) # to go to x
    second = dijkstra(x) # return from x
    result = max(result, first[x] + second[i])

print(result)