[백준] 1238 파티 -python 파이썬

문제

 

 

 

 

처음 이 문제를 접했을 때 한 정점에서 각 정점까지의 최단거리를 구하는 다익스트라 알고리즘을 써야겠다. 라고 생각을 했는데 문제는

이 문제에서 물어보는 것은 왕복 거리라는 거다.

 

 

그래서 여기서 구해줘야하는 것은

 

1. i번 정점 -> x정점 까지의 최단 거리
2. x 정점 -> i 번 정점까지 최단 거리

 

이 둘을 합한 값이 최대인 값을 구해주면 된다.

 

 

그러기 위해서는 다익스트라 알고리즘을 모든 정점을 시작 노드로 주고 구해주면 된다. 

그리고 1번 + 2번의 값을 정해서 최대값을 찾아주면된다.

 

정답 코드

import heapq
n, m, x = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    s,e,t = map(int,input().split())
    graph[s].append((t,e))

def dijkstra(start):
    dp = [1e9]* (n+1)
    heap = []
    dp[start] = 0
    heapq.heappush(heap,(0,start))
    while(heap):
        wei,now = heapq.heappop(heap)

        if dp[now]< wei:
            continue
        for w, nxt in graph[now]:
            nxt_w = w + wei
            if nxt_w < dp[nxt]:
                dp[nxt] = nxt_w
                heapq.heappush(heap,(nxt_w,nxt))
    return dp
#i 번 도시 -> x번도시
come = dijkstra(x)

#x번 도시 -> i번도시 구하기
back = [0]*(n+1)
for i in range(1,n+1):
    if i!= x:
        tmp = dijkstra(i)
        back[i] = tmp[x]
ans = 0
for i in range(1,n+1):
    
    #i번 도시 -> x번 도시 최단거리 + x번 도시 -> i번 도시 최단거리의 최대값
    ans = max(ans,come[i]+back[i])

print(ans)