[백준 1238] 파티- python (solved.ac - 골드 3)

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

1238번: 파티

풀이

문제를 보았을때 알수있는 힌트

요즘 다익스트라 문제를 많이 푸는것같은데 리스트에 거리가 있는 경우는 거의 다익스트라 알고리즘으로 풀면 되는 문제인듯하다.

최단 시간에 오는 문제로 모든 학생들의 정해진 위치까지의 최단 거리와 다시 돌아가는 거리를 더해서 가장 오래걸리는 학생의 소요시간을 출력하면 되는 문제이다.

 

import sys
import heapq
INF = 1e9
input = sys.stdin.readline

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((b,c))
result=[]
for j in range(1,n+1):
    q =[]
    graph_distance = [INF for _ in range(n+1)]
    heapq.heappush(q,(0,j))
    graph_distance[j]=0
    while q:
        v= heapq.heappop(q)
        if graph_distance[v[1]]>=v[0]:
            for i in graph[v[1]]:
                cost = graph_distance[v[1]]+i[1]
                if cost < graph_distance[i[0]]:
                    graph_distance[i[0]]=cost
                    heapq.heappush(q,(cost,i[0]))
    if j == x:
        return_x=graph_distance[1:]
        result.append(0)
        # print(graph_distance[1:])
    else:
        result.append(graph_distance[1:][x-1])

# print(result)
answer=[]
for i in range(n):
    answer.append(result[i]+return_x[i])
print(max(answer))

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1238.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리