[알고리즘] 다익스트라 - 백준 18352 1446 1916 5972 13549 17396

최단 거리 알고리즘

 

18352 특정 거리의 도시 찾기

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
N, M, K, X = map(int, input().split())

graph = [[] for _ in range(N+1)]
distance = [INF] * (N+1)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append((b, 1))

def dijk(start):    # 시작 노드 넣으면
    q = []
    heapq.heappush(q, (0, start))   # 힙큐에 스타트 노드 넣고
    distance[start] = 0 # 당연히 거리는 0
    
    while q:    # 큐가 안비어있으면
        dist, now = heapq.heappop(q)    # 거리랑 현재 노드 뽑아
        if distance[now] < dist:    # 현재 노드 거리가 < 거리
            continue    # 넘겨
        for j in graph[now]:    # 그래프[현재노드]
            cost = dist + j[1]  # 비용은 거리에다 비용 더해
            if cost < distance[j[0]]:   # 코스트가 거리보다 적으면
                distance[j[0]] = cost   # 비용
                heapq.heappush(q, (cost, j[0])) # 집어넣어 큐에
                
dijk(X)

answer = []
for i in range(1, N+1):
    if distance[i] == K:
        answer.append(i)
        
if len(answer) == 0:
    print(-1)
else:
    for x in answer:
        print(x)

 

1446 지름길

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

N, D = map(int, input().split())

graph = [[] for _ in range(D+1)]
distance = [INF]*(D+1)


    
def dijk(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        a, b = heapq.heappop(q)
        if distance[b] < a:
            continue
        for j in graph[b]:
            cost = a + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost
                heapq.heappush(q, (cost, j[0]))


for i in range(D):
    graph[i].append((i+1, 1))
    
for _ in range(N):
    s, d, l = map(int, input().split())
    if d > D:
        continue
    graph[s].append((d, l))
    
dijk(0)
print(distance[D])

 

1916 최소비용 구하기

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

N = int(input())
M = int(input())

graph = [[] for _ in range(N+1)]
cost = [INF] * (N+1)

for _ in range(M):
    s, d, c = map(int, input().split())
    graph[s].append((d, c))


start, end = map(int, input().split())

    
def dijk(x):
    q = []
    heapq.heappush(q, (x, 0))
    cost[x] = 0
    
    while q:
        a, b = heapq.heappop(q)
        if cost[a] < b:
            continue
        for l, r in graph[a]:
            ds = b + r
            
            if cost[l] > ds:
                heapq.heappush(q, (l, ds))
                cost[l] = ds

dijk(start)
print(cost[end])

 

5972 택배 배송

import sys
import heapq

input = sys.stdin.readline

INF = int(1e9)

N, M = map(int, input().split())

graph = [[] for _ in range(N+1)]
distance = [INF] * (N+1)

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))
    
def dijk(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
                
dijk(1)
print(distance[-1])

 

13549 숨바꼭질 3

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)

N, K = map(int, input().split())

dp = [INF] * 100001

def dijk(n, k):
    q = []
    if k <= n:
        print(n-k)
        return
    heapq.heappush(q, [0, n])
    while q:
        a, b = heapq.heappop(q)
        for dx in [b+1, b-1, b*2]:
            if 0 <= dx <= 100000:
                if dx == b*2 and dp[dx] == INF:
                    dp[dx] = a
                    heapq.heappush(q, [a, dx])
                elif dp[dx] == INF:
                    dp[dx] = a + 1
                    heapq.heappush(q, [a+1, dx])
                    
    print(dp[k])
    
dijk(N, K)

 

17396 백도어

 

import sys
import heapq

INF = sys.maxsize
input = sys.stdin.readline

N, M = map(int, input().split())

see = list(map(int, input().split()))

see[-1] = 0

graph = [[] for _ in range(N)]

for i in range(M):
    a,b,c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
    
q = []
heapq.heappush(q, (0, 0))
dp = [INF for _ in range(N)]
dp[0] = 0

while q:
    w, n = heapq.heappop(q)
    if dp[n] < w:
        continue
    else:
        for nx, nw in graph[n]:
            cost = nw + w
            if dp[nx] > cost and see[nx] == 0:
                dp[nx] = cost
                heapq.heappush(q, (cost, nx))
                
print(dp[N-1] if dp[N-1] < INF else -1)

다익은 패턴이 있는 것 같다.