[백준-1238] 파티 - Python

 

 

 

 

 

 

문제 소개

 

 

문제

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

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

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

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

 

사용한 알고리즘

 

다익스트라 알고리즘 적용
크게 다른건 없고 Graph가 단방향이라는것이 유의 해야하고 Dijkstra(A,X) + Dijkstra(X,A) 를 구해야 한다는것의 유의하자

 

 

 

 

 

 

Code 

 

#############################################################################
#
#############################################################################

import sys
import collections
import heapq


sys.stdin = open("input.txt", "r")

input=sys.stdin.readline

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


graph = collections.defaultdict(list)

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



def dijkstra(startN):
    distances_set = { node : float("inf") for node in range(1,N+1) }
    Q = []
    heapq.heappush(Q,[0,startN])
    distances_set[startN]=0

    while Q:
        cur_dist , cur_node = heapq.heappop(Q)

        if len(graph[cur_node][0])>0:
            for next_node,next_dist in graph[cur_node]:
                test_dist = next_dist+cur_dist

                if distances_set[next_node]>test_dist:
                    distances_set[next_node]=test_dist
                    heapq.heappush(Q,[test_dist,next_node])
    return distances_set




max_dist = 0
for k in range(1,N+1):
    LL = dijkstra(k)[X]+dijkstra(X)[k]
    if LL > max_dist:
        max_dist=LL

print(max_dist)

 

 

 

마무리

 

기본적인 다익스트라 적용 문제

 

※ end