백준 1238 : 파티 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline

def Dijkstar(start,end):

    heap=[] ; heapq.heappush(heap,(0,start))
    dp=[INF]*(N+1) ; dp[start]=0

    while heap:

        value,node=heapq.heappop(heap)

        if dp[node]<value:
            continue

        for next_value,next_node in graph[node]:

            next_value+=value


            if next_value<dp[next_node]:

                dp[next_node]=next_value
                heapq.heappush(heap,(next_value,next_node))

    return dp[end]


INF=int(1e9)
N,M,X=map(int,input().split())

graph=[ [] for _ in range(N+1) ]

for i in range(M):
    a,b,c=map(int,input().split())
    graph[a].append((c,b)) #단방향 , 가중치 먼저


Answer=[]
for i in range(N):

    Answer.append(Dijkstar(i+1,X) + Dijkstar(X,i+1))

print(max(Answer))

📌 어떻게 접근할 것인가?

다익스트라 응용 문제입니다.

일단 문제에 요구하는 것을 보면 $N$ 이 먼저 주어집니다. 이때 1,2,3...$N$ 과 같이 1번부터 $N$ 번째 마을에 학생이 한명이 존재한다는 뜻입니다.

이후 파티가 열리는 $X$ 입니다. 문제에서 주어지는 간선을 통해서 파티의 장소에 도착해야합니다.

이때

• 3 4 5

3와 4를 연결하는 간선이 존재하고 가중치가 5라는 입력이 주어졌을때
3에서 4로 가는것은 가능하지만 4에서 3으로 가는것은 불가능합니다.

그리고 파티에 도착했으면 다시 원래 자신이 있던 마을로 돌아가야합니다.

예를들어 $2$ 번 마을에있는 사람이 $3$ 번 마을에 축제가 열렸을때 최단경로로 $2$ - $3$ - $2$ 와 같이 이동해야합니다.

그리고 1번부터 $N$ 번 사람까지 모두 최단경로로 축제가 열리는 마을까지 간다음에 다시 자신의 마을로 돌아오는 값들 중에서 최대값을 찾으면 됩니다.

즉 최단경로의 최소값 중에 $N$ 개 중에 최대값을 구하면 됩니다.