[BOJ] 파티

Jaden Kim·2022년 3월 18일
0

사용한 알고리즘/자료구조

각 학생들이 X마을로 가는 최소 비용과, X마을에서 돌아오는 최소 비용을 각각 구하고, 오고가는 비용의 합이 가장 큰 학생을 찾아야 하는 문제이다.
X마을에서 돌아오는 비용은 시작지점을 X로 다익스트라 알고리즘을 이용하여 계산하면 되고,
X마을로 가는 비용은 입력받은 그래프를 역으로 저장한 뒤, 마찬가지로 시작점을 X로 두고 다익스트라를 적용하면 된다.

코드

from sys import stdin
from collections import deque
INF = int(1e9)
input = stdin.readline

N, M, X = map(int, input().split())
X -= 1
graph = [[] for _ in range(N)]
reverse_graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a-1].append((b-1, c))
    reverse_graph[b-1].append((a-1, c))

def dijstra(graph, X):
    dist_list = [INF]*N
    dist_list[X] = 0
    q = deque([(X, 0)])
    while q:
        x, d = q.popleft()
        if dist_list[x] < d:
            continue
        for xx, dd in graph[x]:
            cost = d + dd
            if cost < dist_list[xx]:
                dist_list[xx] = cost
                q.append((xx, cost))
    return dist_list

to_dist = dijstra(graph, X)
from_dist = dijstra(reverse_graph, X)
print(max([a+b for a, b in zip(to_dist, from_dist)]))

0개의 댓글