[파이썬] 백준 10282 : 해킹 (골드4)

[파이썬] 백준 10282 : 해킹 (골드4))

• https://www.acmicpc.net/problem/10282

---

풀이

방향성 생각

• 방향 그래프
• 시작점이 주어지면 탐색을 통해서 각 노드에 도달하는 시간을 기록해야한다.
• 간선의 가중치가 다르니 다익스트라로 진행

전체코드

import sys
import heapq as hq

input = lambda : sys.stdin.readline().rstrip()
INF = 1e9

def dijkstra(N,x):
    # 각 노드에 최대값 할당
    visit = [1e9]*(N+1)
    visit[x] = 0
    # 시작점 힙에 넣고 시작
    heap = []
    hq.heappush(heap,(0,x))
    while heap:
        t,x = hq.heappop(heap)
        for nx,nt in graphs[x]:
            cost = t+nt
            # x노드까지 t로 간 후, 감염시키는데 걸리는 시간 nt를 더한 시간이 기록된 시간보다 짧으면 갱신하고 힙에추가
            if cost < visit[nx]:
                visit[nx] = cost
                hq.heappush(heap,(cost,nx))
    # 감염시킬 수 있는 컴퓨터의 개수와 걸리는 시간 최대값 기록
    cnt,max_t = 0,0
    for t in visit:
        if t != INF:
            cnt += 1
            max_t = max(max_t,t)
    return cnt,max_t

for _ in range(int(input())):
    N,D,C = map(int,input().split())
    graphs = [[] for _ in range(N+1)]
    for _ in range(D):
        a,b,s = map(int,input().split())
        graphs[b].append((a,s))
    print(*dijkstra(N,C))

코멘트

• 기본 다익스트라 문제