[백준] 1238 파티 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1238
• 🔑 다익스트라
  • 각 마을에서 도착지까지의 거리를 저장 [INF, 1, 0, 3, 7]
  • 도착지에서 각 마을까지의 거리를 저장 [    0, 4, 0, 6, 3]
  • 그래서 총 n번의 다익스트라를 진행
  • 0번 인덱스 제외 각 인덱스의 합이 가장 큰 거리가 정답

 

from collections import defaultdict
from heapq import heappush, heappop

n, m, x = map(int, input().split()) # n명 학생(마을), m개의 단방향 도로, x도착지

graph = defaultdict(list)
for i in range(m):
    s, e, t = map(int, input().split())
    graph[s].append((t, e))             # 거리, 도착지 순서

def dijkstra(start):
    distance = [INF] * (n+1)
    distance[start] = 0
    q = []
    heappush(q, (0, start))             #  거리, 시작위치

    while q:
        now_distance, now_node = heappop(q)

        if now_distance > distance[now_node]:
            continue

        for next_distance, next_node in graph[now_node]:
            new_distance = now_distance + next_distance
            if distance[next_node] > new_distance:
                distance[next_node] = new_distance
                heappush(q, (new_distance, next_node))
    
    sum_distance[start] = distance[x]       # 출발 마을에서 도착 마을까지의 최소 거리를 저장
    return distance

INF = int(1e9)
sum_distance = [0] * (n+1)
x_distance = []

for i in range(1, n+1):
    if i == x:
        x_distance = dijkstra(i)            # 도착지에서 각 마을로 가는 최소 거리를 저장
    else:
        dijkstra(i)

answer = -1
for i in range(1, n+1):     # 왕복 거리가 가장 긴 마을 구하기
    answer = max(answer, x_distance[i] + sum_distance[i])

print(answer)