백준 10282번 해킹(파이썬)

728x90
반응형

www.acmicpc.net/problem/10282

 

10282번: 해킹

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 ��

www.acmicpc.net

다익스트라 유형 

import sys
import collections
import heapq

t=int(sys.stdin.readline())


for kk in range(t):
    n,d,c=map(int,sys.stdin.readline().split())
    graph=collections.defaultdict(list)
    for i in range(d):
        a,b,s=map(int,sys.stdin.readline().split())
        graph[b].append((a,s))

    dist=collections.defaultdict(int)
    q=[(0,c)]
    while q:
        time,node=heapq.heappop(q)
        if node not in dist:
            dist[node]=time
            for v,w in graph[node]:
                alt=time+w
                heapq.heappush(q,(alt,v))
    print(len(dist),max(dist.values()),end=' ')
    print()

 

 

728x90
반응형

'백준' 카테고리의 다른 글

[백준] 1766번 문제집 (위상정렬, 우선순위큐, 파이썬)  (0) 2020.10.10
[백준] 2252번 줄세우기( 파이썬, 위상정렬)  (0) 2020.10.10
백준 1753번 다익스트라 (파이썬)  (0) 2020.10.08
[백준] 1260번 bfs와 dfs (python, java)  (0) 2020.10.07
백준 중앙값 구하기 (우선순위큐, python)  (0) 2020.10.03
TAGS.

Comments