[BOJ 1916] 최소비용구하기

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

 

[풀이]

전형적인 다익스트라 문제.

단, A에서 B로 가는 길이 여러개일 수 있다는 함정이 존재!

그래서 간단히 처음에 가장 최소인 친구들로만 그래프를 구성해주면 된다.

from heapq import heappush,heappop
import sys
def solution(s,d,X):
    x=X[s-1]
    q=[]
    v=[0]*len(x)

    for idx,i in enumerate(x):
        heappush(q,(i,idx))
    while True:
        cur_w,cur_s=heappop(q)
        if v[cur_s]==0:
            if cur_s==d-1:
                return cur_w
            for idx,i in enumerate(X[cur_s]):
                if x[idx]>cur_w+X[cur_s][idx]:
                    x[idx]=cur_w+X[cur_s][idx]
                    heappush(q,(x[idx],idx))
            
            v[cur_s]=1
        
    

N=int(sys.stdin.readline())
M=int(sys.stdin.readline())
X=[[987654321 for i in range(N)]for j in range(N)]
for i in range(M):
    i,j,w=map(int,sys.stdin.readline().split(' '))
    if X[i-1][j-1]>w:
        X[i-1][j-1]=w
s,d=map(int,sys.stdin.readline().split(' '))
print(solution(s,d,X))

평소에 다익스트라 풀때는  dictionary로 그래프를 구성하는 편이다.

index를 불러올때 O(nlogn)의 복잡도를 갖는다하여..

오늘은 무슨일인지 그냥 2차원 배열에 넣어보고 싶었다.ㅎㅎ