[백준] 1238번 파티 [Python] - 데이크스트라

 

 

N개의 마을마다 한 명의 학생이 있고, 어느 날 X번 마을에 모여서 파티를 한다.

M개의 단방향 도로가 있고, 시작 도시 A, 도착 도시 B, 소요시간 T가 정보로 주어진다.

 

각 학생이 자신의 마을에서 X 마을에 모여 파티를 참석하고

자신의 마을로 다시 돌아오는 데 드는

최단 이동 소요시간 중 최대 값을 구하는 문제

 

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X $(1 ≤ X ≤ N)$번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 $T_{i}$$(1 ≤ Ti ≤ 100)$의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N$(1 ≤ N ≤ 1,000)$, M$(1 ≤ M ≤ 10,000)$, X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 $T_{i}$가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

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

 

모든 마을에서 X 마을로 가는 경우--$($1$)$와 X 마을에서 모든 마을로 가는 경우--$($2$)$의 최단 소요시간을 구하고

합을 비교해서 가장 큰 값을 출력하면 된다.

 

 

1번 경우는 다익스트라 알고리즘으로 구할 수 있다.

모든 마을에서 X 마을가 가는데 걸리는 시간을 저장하는 리스트를 생성한다.

초기값은 아주 큰 값으로 설정하고, X마을은 이동을 안하므로 초기값을 0으로 설정한다.

 

아무 마을에서 시작해서 연결된 마을로 가는 소요 시간을 최솟값으로 업데이트 한다.

heapq를 이용해서 탐색하는 과정에서 소요 시간이 낮은 도시의 탐색을 우선함으로써 불필요한 탐색을 줄인다.

 

 

2번 경우도 사실 1번 경우와 같이 구할 수 있다.

출발, 도착을 반대로 저장한 정보로 모든 마을에서 X 마을로 가는 데 걸리는 시간을 구하면

실제로는 X 마을에서 모든 마을로 가는 데 걸리는 시간을 구할 수 있다.

 

 

마지막으로 1, 2 번 경우에서 구한 값을 더한 값 중에서 최댓값을 출력한다.

 

import sys
from heapq import heappop, heappush

def main():
    input = sys.stdin.readline

    INF = float('inf')
    N, M, X = map(int, input().split())
    graph1 = [[] for _ in range(N+1)]
    graph2 = [[] for _ in range(N+1)]
    ans = 0
    for _ in range(M):
        s, e, w = map(int, input().split())
        graph1[s].append((e, w))
        graph2[e].append((s, w))

    def dijkstra(X, graph):
        dist = [INF] * (N+1)
        dist[X] = 0
        q = [(0, X)]
        while q:
            w0, n0 = heappop(q)
            if w0 > dist[n0]:  # -> w0+w1 > dist[n0] -> 업데이트 어차피 x -> continue
                continue
            for n1, w1 in graph[n0]:
                w = w0 + w1
                if w < dist[n1]:
                    dist[n1] = w
                    heappush(q, (w, n1))
        return dist[1:]

    for i, j in zip(dijkstra(X, graph1), dijkstra(X, graph2)):
        if ans < i + j:
            ans = i + j
    print(ans)

if __name__ == "__main__":
    main()

 

 

예제 입력 1 

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 1 

10