백준 11404 플로이드 파이썬 풀이

난이도 : 골드4
풀이일 : 2402095
https://www.acmicpc.net/problem/11404

11404번: 플로이드

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import sys, heapq

def minicost(num):
    # visited 숫자는 최대치로 설정
    visited = [int(1e9)] * (n + 1)

    # visited[num]까지의 비용 0
    visited[num] = 0
    queue = []
    heapq.heappush(queue, [0, num])

    while queue:
        # 가장 작은 cost 부터 탐색
        cost, x = heapq.heappop(queue)

        # cost 가 visited[x] 보다 크다면 중단
        if cost <= visited[x]:
            # 출발지가 x인 길들의 비용, 목적지
            for add, nx in load[x]:
                # 현재 경로가 최소경로라면 갱신 후 힙 추가
                if visited[nx] > cost + add:
                    visited[nx] = cost + add
                    heapq.heappush(queue, [cost + add, nx])

    # 1 ~ n 까지의 최소비용 출력
    for i in range(1, n + 1):
        print(visited[i] if visited[i] != int(1e9) else 0, end=" ")

    return print()

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
load = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b, c = list(map(int, sys.stdin.readline().split()))
    load[a].append([c, b])

# 1 ~ n 까지 각 출발지에서의 모든 도착지까지 최소 비용 탐색
for i in range(1, n + 1):
    minicost(i)

• 1 ~ n 까지 각 출발지에서 모든 도착지로의 최소비용을 구하는 문제였다.
• 힙큐를 사용해서 풀이하였다.

---

느낀점

• 다른 문제를 몇 개는 들쑤시다가 못 풀어내고 결국 다시 최소비용 구하기로 돌아온 느낌. 좋게 말하면 유형뿌시기, 나쁘게 말하면 날로먹는 하루
• 처음엔 술먹고 풀어서 다 맞는데 왜 안되나 한참 생각했는데, heapq에 추가할 때 nx대신 x를 넘겨줘서 그런거였다. 맨 정신에 알고리즘을 풀자