[BOJ/백준] 16188 달빛 여우

import sys
import heapq
input = sys.stdin.readline
def dijkstra_fox():
    distance = [INF for _ in range(N+1)]

    distance[1] = 0
    node_list = []
    heapq.heappush(node_list,(0,1))

    while node_list:
        dis,cur_node = heapq.heappop(node_list)
        if distance[cur_node] < dis:
            continue

        for next_node in graph[cur_node]:
            
            if distance[next_node] > graph[cur_node][next_node] + dis:
                distance[next_node] = graph[cur_node][next_node] + dis
                heapq.heappush(node_list,(distance[next_node],next_node))
    return distance


def dijkstra_wolf():
    distance = [[INF for _ in range(N+1)] for _ in range(2)]
    distance[1][1] = 0
    node_list = []
    heapq.heappush(node_list,(0,1,1))

    while node_list:
        dis,cur_node,turn = heapq.heappop(node_list)
        turn = turn%2
        next_turn = (turn+1)%2
        if distance[turn][cur_node] < dis:
            continue
        for next_node in graph[cur_node]:
            if turn:
                next_distance = dis + graph[cur_node][next_node]//2
            else:
                next_distance = dis + graph[cur_node][next_node]*2
            
            if distance[next_turn][next_node] > next_distance:
                distance[next_turn][next_node] = next_distance
                heapq.heappush(node_list,(next_distance,next_node,next_turn))
    return distance
N,M = map(int,input().split())

graph = [{} for _ in range(N+1)]

for _ in range(M):
    x,y,d = map(int,input().split())
    graph[x][y] = d*2
    graph[y][x] = d*2

INF= float('inf')




distance_fox = dijkstra_fox()
distance_wolf = dijkstra_wolf()
result = 0
for i in range(2,N+1):
    if distance_fox[i] < distance_wolf[0][i] and distance_fox[i] < distance_wolf[1][i]:
        result += 1

print(result)

 

 

어려웠던 문제였다.

 

 이 문제는 다음과 같이 풀면된다. wolf일때 2개의 turn으로 나누어서 distance에 저장을 시켜준다.

 

현재 turn의 distance에 저장하는 것이 아닌 next_turn에 저장을 하고 그 값을 비교하는 것에 조심해주면 된다.

 

그리고 제일 주의해야할 것은 가장 처음 시작하는 노드를 0으로 초기화할때 가장 첫턴 1턴 1번 노드만 0으로

 

초기화 시켜야 한다

 

이를 지키지 않고 둘다 초기화 시키면,, 틀렸습닏를 볼 수 있을 것이다.