[백준 1922] 네트워크 연결

문제

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

알고리즘

1. 연결관계를 dict에 저장한다

2. 다익스트라 알고리즘으로 최단 경로를 탐색한다 

3. 모든 네트워크가 연결되어야 하므로 1번부터 끝 번인 N번까지 탐색 하여 최소 값을 업데이트 한다 

코드

import sys, math, heapq

def Input_Data():
    input = sys.stdin.readline
    N = int(input())
    M = int(input())
    adj = {i : [] for i in range(1,N+1)}
    for _ in range(M):
        a,b,c = map(int, input().split())
        adj[a].append([b,c])
        adj[b].append([a,c])
    return N, M, adj

def Dijkstra(start):
    heap = []
    heapq.heappush(heap,(0, start))
    dist = [math.inf] * (N+1)
    while heap:
        cst, cur = heapq.heappop(heap)
        if cst > dist[cur]: continue
        for neighbor, cost in adj[cur]:
            distance = cst + cost
            if distance < dist[cur]:
                dist[neighbor] = distance
                heapq.heappush(heap,(distance,neighbor))
    print(dist)
    return min(dist)


N, M, adj = Input_Data()
ans = math.inf
# Dijkstra(1)
for i in range(1,N):
    ans += min(ans, Dijkstra(i))
print(ans)