백준 1238 파티

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

 

 이 문제는 단방향 엣지가 주어진 그래프에서, 모든 노드에서 특정 노드로  최단거리로 왕복했을 때의 최댓값을 구하는 문제이다. 

 

 이 문제는 다익스트라 알고리즘을 사용하면 간편하게 풀 수 있다. 다만 오고 갈 때가 다르기에, 필자는 올때의 그래프, 갈때의 그래프를 따로 만들고 시작점을 X로 하여 모든 노드로 가는 최단거리를 구하고 각 인덱스에서 더해서 최댓값을 구했다.

 X를 도착으로 하든 시작으로 하든, 어차피 그래프만 거꾸로 뒤집으면 X를 시작으로 하여, 오고가는 것을 다 커버할 수 있다.

import sys
input = sys.stdin.readline
import math
import heapq

def dijkstra(start,graph):
    d=[math.inf for _ in range(N+1)]
    d[start]=0

    heap = []
    heapq.heappush(heap,[0,start])

    while heap:
        cur_w,cur_n = heapq.heappop(heap)

        for next_w,next_n in graph[cur_n]:
            if cur_w+next_w < d[next_n]:
                d[next_n] = cur_w+next_w
                heapq.heappush(heap,[d[next_n],next_n])
    
    return d[1:]

N,M,X = map(int,input().rstrip().split())
go_graph=[[] for _ in range(N+1)]#X에서 출발
come_graph=[[] for _ in range(N+1)]#반대로 하여,X에서 출발

for _ in range(M):
    s,e,c = map(int,input().rstrip().split())
    go_graph[s].append([c,e])
    come_graph[e].append([c,s])

go=dijkstra(X,go_graph)
come=dijkstra(X,come_graph)
max_=-1

for i in range(N):
    if go[i]+come[i] > max_:
        max_=go[i]+come[i]

print(max_)