[Python] 1238-백준-파티

1. 문제 출처

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

1238번: 파티

2. 풀이

각 노드를 시작점으로 경로를 구해줘야 한다.

 

import heapq
# 입력
n,m,x = map(int, input().split())

graph = [[] for _ in range(n+1)]
distance = [[float('inf')] * (n+1) for _ in range(n+1)]

# 입력
for _ in range(m):
    start , end , cost = map(int, input().split())
    graph[start].append([cost , end])
 
# 데이크스트라 알고리즘 
def di(start):
    q = []
    heapq.heappush(q,[0,start])
    distance[start][start] = 0
    
    while q:
        dist, node = heapq.heappop(q)
        if distance[start][node] < dist:
            continue
            
        for w,n in graph[node]:
            cost = dist+ w
            if distance[start][n]>cost:
                distance[start][n] = cost
                heapq.heappush(q,[cost,n])
                

def solution():
    # 모든 경로에 따라 데아크스트라 알고리즘을 통해 비용을 구한다.
    for i in range(1,n+1):
        di(i)
    result = []
    # 왕복거리 리스트를 구한다.
    for i in range(1,n+1):
        if i == x: 
            continue
        result.append(distance[x][i] + distance[i][x])
    print(max(result))    

solution()