백준 / 1238번 / 파티 / python 파이썬

 

 

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

 

 

---

나의 풀이

import heapq

def dijkstra(start):
    distances = [float('inf')] * (N + 1)
    distances[start] = 0
    pq = []   
    heapq.heappush(pq, (0, start))  
    
    while pq:
        dist, now = heapq.heappop(pq)   
        if distances[now] >= dist:  
            for next_node, time in graph[now]:  
                if dist + time < distances[next_node]:  
                    distances[next_node] = dist + time
                    heapq.heappush(pq, (dist + time, next_node))  
    
    return distances

N, M, X = map(int, input().split())
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b, time = map(int, input().split())
    graph[a].append((time, b))  

distances_from_X = dijkstra(X)  

for i in range(1, N + 1):
    if i != X:
        reverse_distances = dijkstra(i) 
        distances_from_X[i] += reverse_distances[X]  

print(max(distances_from_X[1:]))

 

다익스트라로 최단 거리를 구해 그 중 가장 거리가 긴 값을 출력한다.