[백준17396] / 백도어 - 다익스트라

 

백준17396

 

푼 날짜 : 2024.11.14

푼 문제 : [17396] / 백도어

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근방식 :

시야가 있는 곳은 계산하지 않고 넘기는 방식에 일반적인 다익스트라 방식으로 계산했다.

 

 

코드 :

import sys
import heapq

input = sys.stdin.readline
INF = float("INF")

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

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

def dijkstra(num):
    heap = [(0, num)]
    dist = [INF for _ in range(N)]
    dist[num] = 0

    while heap:
        now_cost, now_node = heapq.heappop(heap)
        if dist[now_node] < now_cost: continue

        for next, cost in graph[now_node]:
            # 상대 넥서스가 아닌 위치에 시야가 있을 경우 진행하지 않는다
            if ward[next] and next != N-1: continue
            # 비용계산
            all_cost = now_cost + cost
            
            if dist[next] > all_cost:
                dist[next] = all_cost
                heapq.heappush(heap, (all_cost, next))
    
    print(dist[N-1] if dist[N-1] != INF else -1)
    
dijkstra(0)

 

 

이 문제를 푸니까 롤이 하고 싶어진다~