[알고리즘 문제풀이] 해킹

문제 제목 : 해킹

문제 난이도 : 중

문제 유형 : 다익스트라 최단경로

https://www.acmicpc.net/problem/10282
시간 제한 : 2초
메모리 제한 : 256MB

문제풀이 아이디어

< 소스코드 >

import heapq
import sys
input = sys.stdin.readline

def dijkstra(start):
    heap_data = []
    heapq.heappush(heap_data, (0, start)) # 시작 정점
    distance[start] = 0
    while heap_data:
        dist, now = heapq.heappop(heap_data)
        if distance[now] < dist:
            continue
        for i in adj[now]:
            cost = dist + i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(heap_data, (cost, i[0]))
                
for _ in range(int(input())):
    n, m, start = map(int, input().split())
    adj = [[] for i in range(n + 1)]
    distance = [1e9] * (n + 1) # Inf로 초기화
    for _ in range(m):
        x, y, cost = map(int, input().split())
        adj[y].append((x, cost)) # y를 하는 이유 의존성 관계때문에 뒤집어서
    dijkstra(start)
    count = 0
    max_distance = 0
    for i in distance:
        if i != 1e9:
            count += 1
            if i > max_distance:
                max_distance = i
    print(count, max_distance)