https://school.programmers.co.kr/learn/courses/30/lessons/81304

from collections import defaultdict
import heapq

def solution(N, start, end, roads, traps):
    
    # INPUT
    edges=defaultdict(list)
    reversed_edges=defaultdict(list)
    for p,q,s in roads:
        edges[p].append((q,s))
        reversed_edges[q].append((p,s))
    
    # Dijkstra
    dist=[-1]*(N+1) # 1-based
    dist[start]=0
    pq=[]
    heapq.heappush(pq,(0,start,False))
    while pq:
        cur_cost,cur_node,trap=heapq.heappop(pq)
        if cur_cost>dist[cur_node]:
            continue
        if not trap:
            for next_node,cost in edges[cur_node]:
                if cur_cost+cost<dist[next_node] and dist[next_node]==-1:
                    dist[next_node]=cur_cost+cost
                    if next_node in traps:
                        heapq.heappush(pq,(cur_cost+cost,next_node,not trap))
                    else:
                        heapq.heappush(pq,(cur_cost+cost,next_node,trap))
        else:
            for next_node,cost in reversed_edges[cur_node]:
                if cur_cost+cost<dist[next_node] and dist[next_node]==-1:
                    dist[next_node]=cur_cost+cost
                    if next_node in traps:
                        heapq.heappush(pq,(cur_cost+cost,next_node,not trap))
                    else:
                        heapq.heappush(pq,(cur_cost+cost,next_node,trap))
    
    return dist[end]

잘못 생각한점 : Trap은 노드별로 “독립적”으로 작동하는데, 나는 그냥 모든 노드에 대해 일괄적으로 적용해버려서 틀림

그리고 문제가 Trap 상태 유무를 전체 edge에 대해 한다고 하더라도, dist[][] 배열을 2차원으로 (trap 유무에 대해서도 상태 저장해야함) 했어야함.

따라서 정리하자면, 다익스트라 + 노드에 상태정보 필요까지는 맞음.

그러나 노드마다 별도로 상태정보를 기재해야한다는 점을 놓쳤음. (문제 제대로 안읽고 안그려봤음)

가장 중요한 거 : “함정 상태”를 들고다녀야 한다.

“노드를 방문하는게 아니라”, “노드&상태를 방문한다” 그리고 그 “상태”는 전체 함정에 대한 상태를 가지고 다녀야한다.

이를 구현하기 위한 자료구조 : 비트 마스킹