[다익스트라] (코드트리) 코드트리 투어

📌  헤맨 점

1️⃣  자기 자신으로 가는 간선이 있어도 최단 거리는 0이다.
(해당 경로가 있을 경우 그 가중치를 초기값으로 설정해서 헤맴)

자기 자신으로 가는 간선이 있을 경우

2️⃣ 500 명령이 주어질때 단순히 출발점만 변경되는 것이 아니라 큐에 있는 모든 아이템의 cost가 출발지점이 변경되었을때로 변경된다.

(출발점만 변경했음 문제를 제대로 읽고 정리해야하는 필요성을 느낌)

 

3️⃣ ❤️‍🔥제일 중요❤️‍🔥 힙에서 특정원소를 삭제할때는 원소의 인덱스를 set으로 별도로 저장하고 set에서만 삭제한다음 힙에서는 while heap and heap[0][1] not in set(): heappop(heap) 으로 처리한다. 즉, 있는 id가 처음이 될때까지 이전에 삭제된 id를 빼주는거다.

이렇게 바로 삭제하는게 아니라 필요할때 삭제해서 시간을 줄일 수 있다. (아름답다..)

 

<<관련 코드>>

    elif orders[0]==300:
        id = orders[1]
        if id in id_set:
            id_set.remove(id)

    elif orders[0]==400:
        while I and I[0][1] not in id_set:
            heappop(I)
        if I:
            minus_profit,idx,revenue,dest = heappop(I)
            if minus_profit>0:
                print(-1)
                heappush(I,(minus_profit,idx,revenue,dest))
            else:
                print(idx)
        else:
            print(-1)

 

 

📌 전체 코드

from heapq import heappop,heappush
import sys
input = sys.stdin.readline
Q =int(input())
start = 0
INF = int(1e9)
G = []
I = []
dic = {}
id_set =set()
def dijkstra(start):
    q = []
    init_w = 0
    heappush(q,(init_w,start))
    distance=[INF]*n
    distance[start]=init_w
    while q:
        cost,v = heappop(q)
        if distance[v]<cost:
            continue
        for nv,nw in G[v]:
            ncost = cost+nw
            if ncost < distance[nv]:
                distance[nv]=ncost
                heappush(q,(ncost,nv))
    return distance
for q_idx in range(Q):
    orders = list(map(int,input().split()))
    if orders[0]==100:
        n,m = orders[1],orders[2]
        G = [[] for _ in range(n)]
        for i in range(1,m+1):
            v,u,w = orders[i*3:i*3+3]
            G[v].append((u,w))
            G[u].append((v,w))

    elif orders[0]==200:
        id,revenue,dest = orders[1],orders[2],orders[3]
        if start not in dic:
            dic[start] = dijkstra(start)
        cost = dic[start][dest]
        heappush(I,(-(revenue-cost),id,revenue,dest))
        id_set.add(id)

    elif orders[0]==300:
        id = orders[1]
        if id in id_set:
            id_set.remove(id)

    elif orders[0]==400:
        while I and I[0][1] not in id_set:
            heappop(I)
        if I:
            minus_profit,idx,revenue,dest = heappop(I)
            if minus_profit>0:
                print(-1)
                heappush(I,(minus_profit,idx,revenue,dest))
            else:
                print(idx)
        else:
            print(-1)

    elif orders[0]==500:
        start = orders[1]
        dic[start] = dijkstra(start)
        temp = []
        while I:
            minus_profit, idx,revenue,dest = heappop(I)
            cost = dic[start][dest]
            temp.append((-(revenue-cost),idx,revenue,dest))  
        for item in temp:
            heappush(I,item)