[백준] CLASS 4 달성하기 4일차

이진규·2022년 7월 29일
1

백준(PYTHON)

목록 보기
60/115

1. 파티(★다익스트라)

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

import heapq
from sys import stdin
input = stdin.readline

n, m, x = map(int, input().split())
graph = [ [] for _ in range(n+1) ]

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

def dijkstra(start):
    q = []
    distance = [1e9] * (n+1) # 최소 거리가 적힌 배열

    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q) # 최소힙 이용

        if distance[now] < dist:
            continue

        for node_index, node_cost in graph[now]:
            cost = dist + node_cost

            if distance[node_index] > cost:
                distance[node_index] = cost
                heapq.heappush(q, (cost, node_index))

    return distance

result = 0
for i in range(1, n+1): # i는 다익스트라를 시작하는 지점을 의미
    go = dijkstra(i)
    back = dijkstra(x)
    result = max(result, go[x] + back[i])

print(result)
profile
항상 궁금해하고 공부하고 기록하자.

0개의 댓글