[백준/Python] 1238 파티

문제

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

1238번: 파티

 

해석

최단거리에 대한 문제이므로 다익스트라를 생각해볼 수 있다. 또한, 문제에 '단방향'이라고 적혀있다. 다익스트라 문제를 풀어보면서 '단방향'이 일반적인 문제이고 여기에 조금 더 심화된 것이 '양방향'인 것 같다. 그래도 결국 다익스트라 로직에서는 크게 벗어나지 않는다.

해당 문제도 '단방향'인 것은 맞지만 왔다가 다시 돌아와야하는 문제이다. 그래서 예제를 보면 2번으로 간 뒤에는 다시 자신의 위치로 돌아가도록 되어있다. 그래서 다익스트라 구현은 하되, distance 배열을 return 해줘야된다. 왜냐하면 목표 지점의 노드의 distance와 출발 지점의 노드 distance를 알고 있어야 두 값을 더해서 최대 시간을 구할 수 있기 때문이다.

그래서 나는 목표 지점의 distance를 미리 만들어놨고, 나머지 출발 지점의 distance는 for문을 이용하여 덧셈을 할 수 있도록 구현했다.

 

코드

import sys
from heapq import *

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

# distance 배열을 사용하기 위해 선언 및 return을 해줘야 한다.
def dijkstra(start):
    distance = [INF] * (n+1)
    q = []
    heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heappop(q)
        if distance[now] < dist:
            continue

        for b, c in graph[now]:
            cost = distance[now] + c
            if cost < distance[b]:
                distance[b] = cost
                heappush(q, (cost, b))
    
    return distance

# goal 은 도착지점이다.
n, m, goal = map(int, input().split())
graph = [[] for i in range(n+1)]

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

max_time = 0
back_distance = dijkstra(goal)

for i in range(1, n+1):
    if i == goal:
        continue
    go_distance = dijkstra(i)
    count_time = back_distance[i] + go_distance[goal]
    max_time = max(max_time, count_time)

print(max_time)