파이썬 | 백준 | 10282 | 해킹

solution : bfs

시간 초과

# 10282, 해킹
import sys
from collections import deque

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

while t:
    # 컴퓨터 개수, 의존성 개수, 해킹당한 컴퓨터 번호
    n, d, c = map(int, sys.stdin.readline().split())

    network = [[] for _ in range(n+1)]
    visited = [1001]*(n+1)
  
    for _ in range(d):
        a, b, s = map(int, sys.stdin.readline().split())
        network[b].append((a, s))

    q = deque()
    q.append(c)
    visited[c] = 0

    while q:
        now = q.popleft()
        for x in network[now]:
            if visited[now] + x[1] <= visited[x[0]]:
                visited[x[0]] = visited[now] + x[1]
                q.append(x[0])

    cnt, sec = 0, 0
    for v in visited:
        if v != 1001:
            cnt += 1
            sec = max(sec, v)
    print(cnt, sec)

    t -= 1

solution : 다익스트라

# 10282, 해킹
import sys
import heapq


def dijkstra(graph, start):
    distances = [float("inf")] * (n + 1)
    distances[start] = 0

    heap = []
    heapq.heappush(heap, (distances[start], start))

    while heap:
        curr_distance, curr_node = heapq.heappop(heap)

        if distances[curr_node] < curr_distance:
            continue

        for x in graph[curr_node]:
            next_distance, next_node = x
            tot_distance = curr_distance + next_distance

            if tot_distance < distances[next_node]:
                distances[next_node] = tot_distance
                heapq.heappush(heap, (tot_distance, next_node))

    cnt = 0
    sec = 0
    for i in distances:
        if i != float("inf"):
            cnt += 1
            sec = max(sec, i)
    print(cnt, sec)


t = int(sys.stdin.readline())
while t:
    # 컴퓨터 개수, 의존성 개수, 해킹당한 컴퓨터 번호
    n, d, c = map(int, sys.stdin.readline().split())
    network = [[] for _ in range(n + 1)]
    for _ in range(d):
        a, b, s = map(int, sys.stdin.readline().split())
        network[b].append((s, a))

    dijkstra(network, c)
    t -= 1

 

문제 출처 www.acmicpc.net/problem/10282

10282번: 해킹