[백준] 10282번 해킹 파이썬 코드

코드

# bfs로 해결할 수 있을 거라 생각했지만, 가중치가 달라서 다익스트라 알고리즘 이용

import sys, heapq
input = sys.stdin.readline
INF = 987654321
tc = int(input())
def dijkstra(node, zido, hi):
  queue = [(0,node)]
  hi[node] = 0
  while queue:
    now, next = heapq.heappop(queue)
    if now > hi[next]: continue
    for i in zido[next]:
      dist = now + i[1]
      if hi[i[0]] > dist:
        hi[i[0]] = dist
        heapq.heappush(queue, (dist, i[0]))

for _ in range(tc):
  n,d,c = map(int, input().split())
  graph = [[] for _ in range(n+1)]
  visited = [INF]*(n+1)
  for _ in range(d):
    a,b,s = map(int, input().split())
    graph[b].append((a,s))
  dijkstra(c,graph, visited)
  cnt = 0
  ans = 0
  for i in visited:
    if i != INF:
      cnt += 1
      ans = max(ans, i)
  print(cnt, ans)

구현까지 잘해두고 출력에 애를 먹었던 문제.