Jinho Tech

골드 3 난이도 치고는 쉬운 다익스트라 알고리즘 문제이다.

N-1개(1->X->1, 2->X->2, ..., N->X->X (X->X->X 제외))의 최단경로 중 최댓값을 출력해주면 된다.

import heapq
import sys
INF = sys.maxsize
# input = sys.stdin.readline

def dijkstra(start, end):
    q = []
    heapq.heappush(q, (0, start))
    dis = [INF]*(N+1)
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))
    return dis[end]
    
N, M, X = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
t = 0
for i in range(1, N+1):
    if i == X:
        continue
    t = max(t, dijkstra(i, X) + dijkstra(X, i))
print(t)