Bronze Cow Party(백준 6248)

 다익스트라 알고리즘으로 출발점에서 각 지점까지 가는 거리 중에서 제일 먼 곳을 찾고 이후에 그 값에 2배를 해주면 된다. 

import sys 
import heapq 
input = sys.stdin.readline 
n,m,x =map(int, input().split())
inf = int(1e9)
dist = [inf for _ in range(n+1)]
gra = [[]for i in range(n+1)]

for i in range(m):
    a,b,c = map(int , input().split())
    gra[a].append((b,c))
    gra[b].append((a,c))
    

def dijk(start):
    q =[]
    dist[start] = 0 
    q.append((0,start)) 
    heapq.heapify(q)
    while q:
        wei ,now  = heapq.heappop(q)
        if dist[now] < wei :
            continue 
        for nextnode, cost in gra[now]:
            if dist[nextnode] > cost + wei :
                dist[nextnode] = cost+wei 
                heapq.heappush(q,(cost+wei , nextnode))
        
dijk(x) 
ans = 0 
for i in range(1,n+1) :
    if dist[i] == inf :
        continue
    if ans < dist[i] :
        ans = dist[i] 
print(ans*2)