[Python] 파티 - 백준 (최단경로)

해당 글은 백준 1238번 '파티' 문제를 다룬다.

문제

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

1238번: 파티

 

설명

해당 문제는 최단 경로를 구하는 알고리즘 중 다익스트라를 활용하면 된다.
x까지 가는 최단 경로와 x에서 집으로 돌아오는 최단 경로를 2번의 다익스트라로 구할 수 있다.
 

코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

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((e, t))

def dijkstra(start, end):
    distance = [INF]*(n+1)
    distance[start]= 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for next_n, next_dist in graph[now]:
            cost = dist + next_dist
            if cost < distance[next_n]:
                distance[next_n] = cost
                heapq.heappush(q, (cost, next_n))
    return distance[end]

result = []
for i in range(1, n+1):
    result.append(dijkstra(i, x)+dijkstra(x, i))
print(max(result))