[python3] 백준 1238 풀이 ( 파티, 다익스트라 )

이번 문제는 참신했다. 물론 내가 생각도 못해서 참신하게 느껴진거 겠지만ㅋㅋ

우선 문제를 보자

문제를 읽어보면 여러 곳에서 학생들이 X마을로 모인다. 이후에 각자 집으로 돌아갈 때 가장 오래 걸리는 학생의 소요 시간을 출력한다.

간단히 생각해보면 파티에 참석하는 경우 마을이 N개 이기 때문에 N -> X로 가는 경우의 수가 나올것이다.
파티가 끝나고 집에 가는 경우는 X -> N으로 가는 경우의 수가 나온다.

그럼 단순하게 보면 단일 시작점 알고리즘이 적용되면 안 되는거 같다. 왜냐하면 출발할 때 N개의 마을에서 각자 출발하기 때문이다. 그래서 나도 플로이드-워샬을 적용하고 풀고자 했다.

N=1000 이므로 N^3 = 1,000,000,000 = 10억, 21억 넘지 않아서 괜찮을 줄 알았다. (찾아보니 1초에 컴퓨터는 1억연산이 가능하다고 한다. 즉 안된다는 소리다.)
당연하게도 플로이드 워샬을 사용한 코드는 시간초과를 뱉어냈다.

그럼 다시 생각해보자. 가능한 방법은 다익스트라나 벨만-포드 같은 경우가 남는다.

우리는 다익스트라를 사용할때 주로 out degree로 인접 리스트(adj)를 나타낸다. (out degree는 해당 노드에서 향하는 차수를 의미한다. )즉, X->N은 단일 시작점 알고리즘이기 때문에 다익스트라로 구할 수 있다.
파티가 시작될때의 경로는 N->X 이다. 출발점이 단일 시작점이 아니기 때문에 다익스트라를 사용할 수 없다.

그럼 거꾸로 생각해보자.
만약 X에서 시작하더라도 자신한테 오는 가장 가까운 in degree부터 추가하는 형식으로 다익스트라를 진행한다면??
그러면 X가 도착점 이더라도 출발점 N에서 X까지의 최솟값을 구할 수 있다.

그럼 결과적으로 다익스트라를 단 2번만 하면 N -> X -> N을 구할 수 있다!!

그럼 끝이다 바로 코딩을 진행하면 된다.

1. out degree형태로 o_adj 배열 구하기
2. in degree형태로 i_adj 배열 구하기
3. 다익스트라(o_adj), 다익스트라(i_adj) 하기
4. 결과를 더하고 가장 큰 값 출력하기

"""
N -> X -> N
원래 다익스트라는 outdegree기준으로 구함.
만약 indegree 기준으로 구한다면? N->X의 값을 구할 수 있다.
그럼 다익스트라 2번하면 N->X->N을 구할수 있다.
"""
import sys
input = sys.stdin.readline
N,M,X = map(int, input().split())

INF = 1000000000
i_adj = [ []for i in range(N+1) ]
o_adj = [ []for i in range(N+1) ]
for _ in range(M):
    a,b,c = map(int, input().split())
    i_adj[b].append((a,c))
    o_adj[a].append((b,c))

import heapq
def daik(pq, adj):
    dp = [INF for i in range(N+1)]
    dp[X] = 0
    while pq:
        cost, node = heapq.heappop(pq)
        if dp[node] < cost:
            continue
        for i in range(len(adj[node])):
            end, endcost = adj[node][i]
            if dp[end] > endcost + cost:
                dp[end] = endcost+cost
                heapq.heappush(pq, (dp[end],end))
    return dp
N_X = daik([(0,X)], i_adj)
X_N = daik([(0,X)], o_adj)

big = 0
for i in range(1, N+1):
    big = max(N_X[i] + X_N[i],big)
print(big)