백준 - 1956번(다익스트라)

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

1956번: 운동

 

import sys
from heapq import heappush,heappop

v,e = map(int,sys.stdin.readline().split())

arr = [[] for _ in range(v+1)]
ans = [[float('inf') for _ in range(v + 1)] for _ in range(v+1)]
q = []
for _ in range(e):
    x,y,z = map(int,sys.stdin.readline().split())
    arr[x].append([y,z])
    ans[x][y] = z
    heappush(q,[z,x,y])

def daijk():
    while q:
        dist,s,e = heappop(q)
        if s == e:
            print(dist)
            break

        if ans[s][e] > dist:
            for i in arr[e]:
                if ans[s][i[0]] >= dist + i[1]:
                    ans[s][i[0]] = dist + i[1]
                    heappush(q, [dist + i[1], s, i[0]])
    else:
        print(-1)

daijk()

다익스트라 응용문제다.

풀이를 찾아보니 플로이드 와샬 알고리즘으로도 풀 수 있다고 한다.

근데 아마 다익스트라 응용이 좀 더 속도가 빠를 것이다.

우선 q에 우선순위 큐를 활용하여 거리가 짧은 순서대로 주어진 값들을 모두 집어넣는다.

ans 배열은 각각 0~v까지 가로 세로가 존재한다.

ans [i][j]의 의미는 i에서 j까지의 최단 경로를 의미한다.

우리는 출발지점과 도착지점이 같은 최단경로를 찾아야 한다.

따라서 i==j를 만족하는 ans [i][j] 중에 답이 있을 것이다.

q에서 s와 e를 각각 출발, 종료 지점으로 둔다.

만약 ans [s][e]가 현재 dist 보다 작을 경우 배열의 값을 바꾸지 않고 그렇지 않은 경우 바꿔준다.

누적된 값과 기존 출발 지점과 새로운 종료 지점을 넣어준다.