1753 - 최단경로

www.acmicpc.net/problem/1753

1753번: 최단경로

5달을 걸친 싸움

후

 

드뎌 풀었네요.

 

해당 문제는 다익스트라 알고리즘을 사용하는 문제인데, 그에 대한 설명은 다른 블로그 분들이 더 잘할거라고 믿습니당.

 

그렇다면 제가 할 일은 도대체 뭐 저렇게 많이 틀렸냐인데, 처음에 C++17로 푼 건 다익스트라가 아니라 최소 간선 BFS를 사용해서 시간 초과가 떴구요.

 

좀 더 자세히 봐야할 코드는 Python입니다.

 

힙을 만들기 싫어서 내장 라이브러리에 있는 걸 가져다 썼더니 대참사 발생

 

from queue import PriorityQueue

이거 썼다가 시간 초과나서

import heapq

혹시나 이거 써보니 통과 되더라고요.

 

아쒸

import sys
import heapq

pq = []
INF = float('inf')

V, E = map(int, sys.stdin.readline().split())

cost = [[] for _ in range(V + 1)]
visited = [INF for _ in range(V + 1)]

K = int(input())
for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    cost[u].append([v, w])

heapq.heappush(pq, [0, K])
visited[K] = 0

while pq:
    co, no = heapq.heappop(pq)
    for arr in cost[no]:
        nxtno, nxtco = arr
        if visited[nxtno] > nxtco + co:
            visited[nxtno] = nxtco + co
            heapq.heappush(pq, [nxtco + co, nxtno])

for _ in visited[1:]:
    if _ == INF:
        print("INF")
    else:
        print(_)

통과 코드입니다.

 

제가 또 실수한 부분은 간선 정보를 배열에 담았다는 점인데요. 

 

노드의 갯수가 20,000개이다 보니 배열에 담으면 총 20,000 x 20,000 = 400,000,000개의 배열이 필요합니다. 당연히 비효율적이죠.

 

그래서 링크드리스트 형태로 담았고요.

 

또 실수한 부분이 있는데, heap에 간선 비용을 넣을 때 누적된 값을 넣어가며, 진행해야하는데 누적하는 것을 하지 않아 틀린 답이 나오기도 했더랬죠.

 

그리고 제일 큰 문제는 앞서 말한 라이브러리 문제가 있었고요.

 

이래서 직접 구현하던가 해야겠네요.

 

게으르면 손해네요.

 

---

이상 1753 - 최단경로였습니다. ^_^