[백준 1238번] 파티 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
import heapq
INF = sys.maxsize

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

graph = [[] for i in range(N+1)]
dij = [[INF]*(N+1) for i in range(N+1)]

for i in range(M):
  x1,x2,t = map(int,input().split())
  graph[x1].append((x2,t))

def Dijkstra(start):
  hq = []
  heapq.heappush(hq,(0,start))

  while hq:
    w,now = heapq.heappop(hq)
    if dij[start][now] <= w:
      continue
    dij[start][now] = w

    for i in graph[now]:
      x1,w1 = i
      heapq.heappush(hq,(w1+w,x1))

for i in range(1,N+1):
  Dijkstra(i)

result = 0
for i in range(1,N+1):
  result = max(dij[i][X]+dij[X][i],result)

print(result)

노드수는 엄청 많은데 (최대 1000개) 간선의 수는 몇개 없는걸 보고 다 익스트라를 써야되는건가? 라고 생각은 했는데, 다 익스트라 코드쓰기가 귀찮아서 쉽고 편한 플로이드를 썼는데 당연하게도 시간초과가 나왔다 ㅋㅋ

 

결국 그냥 다 익스트라 N번 때리고 정답을 구했다.

 

 

오늘의 교훈) 문제의 조건을 잘 읽고 적절한 알고리즘을 선택하자