2023 하계모각코4회차 개인 목표 및 결과

일시

2023-07-29 13:00~ 16:00

목표

4회차에서는 다익스트라 알고리즘 문제를 풀어볼 생각이다.

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

10282번: 해킹

결과

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
inf = sys.maxsize

def dijkstra(start, dp, graph):
    heappush(heap, [0, start])
    dp[start] = 0
    while heap:
        w, n = heappop(heap)
        for n_n, wei in graph[n]:
            n_w = wei + w
            if n_w < dp[n_n]:
                dp[n_n] = n_w
                heappush(heap, [n_w, n_n])

t = int(input())
for _ in range(t):
    n, d, c = map(int ,input().split())
    graph = [[] for _ in range(n + 1)]
    dp = [inf] * (n + 1)
    heap = []
    for _ in range(d):
        a, b, s = map(int, input().split())
        graph[b].append([a, s])

    dijkstra(c, dp, graph)

    cnt = 0
    ans = 0
    for i in dp:
        if i != inf:
            cnt += 1
            ans = max(ans, i)

    print(f"{cnt} {ans}")

다익스트라 알고리즘을 푸는데 아직 부족한 것 같다는 생각을 했다