10282 해킹

www.acmicpc.net/problem/10282

10282번: 해킹

 

다익스트라 문제인데 약간의 변형이 있다.

 

핵심은 다음과 같다.

1. a,b,s로 주어져도 의존성정의에 의해 b->a로 가능 비용이 s이다. 평소처럼 a->b가 s라고 생각하면 안된다.

2. INF가 아닌 값들을 카운트하면 총 감염된 컴퓨터 개수가 나온다.

3. INF를 제외한 distance에서 가장 큰값이 가장 마지막에 감염된 컴퓨터시간으로 정의하면 된다.

 

import sys
input = sys.stdin.readline

import heapq

T = int(input())

INF = int(1e9)

def countHacked(arr):
  return len(list(filter(lambda x: x!=-1, arr)))

answer = []

for _ in range(T):
  n,d,start = map(int, input().rstrip().split(" "))
  info = dict()
  visited = [0] * (1+n)
  distance = [INF] * (1+n)

  for i in range(1, n+1):
    info[i] = []
  
  for __ in range(d):
    b,a,s = map(int, input().rstrip().split(" "))
    info[a].append( (b,s) )
  

  q = []
  heapq.heappush(q, (0, start))
  distance[start] = 0
  
  while( len(q) != 0 ):
    weight, curr = heapq.heappop(q)
    visited[curr] = 1
    
    for i in info[curr]:
      dest, cost = i
      if( visited[dest] == 0 ):
        if( distance[dest] > weight + cost):
          distance[dest] = weight+cost
          heapq.heappush(q, (distance[dest], dest))
  
  for i in range(len(distance)):
    if(distance[i] == INF):
      distance[i] = -1
  
  answer.append( (countHacked(distance), max(distance) ))

for i in answer:
  print(" ".join(map(str, i)))