bright

programmers.co.kr/learn/courses/30/lessons/42626#

def solution(scoville, K):
    import heapq
    answer = 0
    heapq.heapify(scoville)

    while scoville:
        first = heapq.heappop(scoville)

        if first >= K:
            break

        if len(scoville) <= 0:
            return -1
        
        second = heapq.heappop(scoville)
        heapq.heappush(scoville, first + second * 2)
        answer += 1
    
    return answer

1) heapq 사용 

2) heapq 초기화 코드 알아두기 ( heapify 사용 ) 

  => 함수에 리스트를 인자로 넘기면 리스트 내부의 원소들의 힙 구조에 맞게 재배치되며 최소값이 0번째 인덱스에 옴

3) while scoville => 인자가 0개인 경우 거르기

4) if len(scoville) <=0  -> 인자가 1개인 경우 거르기 ( 하나 꺼냈으니까 안남으면 1개였던 것 ) 

5) 인자가 2개 이상 남았으면 합치기 도전해보기 

www.acmicpc.net/problem/1238

import heapq
import sys
input = sys.stdin.readline 

n, m, x = map(int,input().split())
# n 명, 도로 m 개 , x 마을에서 

graph= [ [] for i in range(n+1)]
for i in range(m):
  a,b,c = map(int,input().split())
  graph[a].append((b,c))

def dij(start):
  q = []
  heapq.heappush(q, (0,start))
  dist = [1e9]*(n+1)
  dist[start] = 0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now]<d : continue 
    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q,(cost,i[0]))
  return dist 

result = [0]
dist_x = dij(x)
for i in range(1,n+1):
  result.append( dij(i)[x] + dist_x[i] ) 

print ( max(result) )

www.acmicpc.net/problem/18352

import heapq
import sys
input = sys.stdin.readline 


n, m, k, x = map(int,input().split())
# 도시 도로 거리 출발 도시 
graph = [ [] for _ in range(n+1) ]
for i in range(m):
  a, b= map(int, input().split())
  graph[a].append(b)

# x에서 출발, 경로가 k 인 도시 오름차순 출력 없으면 -1 

def dij(start):
  q = []
  heapq.heappush(q, (0,start))
  dist = [1e9]*(n+1)
  dist[start]=0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now]<d : continue 
    
    for i in graph[now]:
      cost = d + 1
      if cost<dist[i]:
        dist[i] = cost 
        heapq.heappush(q, (cost,i))
  return dist 

result = dij(x)
answer = []

for i in range(n+1) : 
  if result[i] == k : 
    answer.append(i)

if answer == [] : print(-1)
else:
  answer.sort()
  for i in answer: print(i)

www.acmicpc.net/problem/1504

import heapq
import sys
input = sys.stdin.readline

n, e = map(int,input().split()) # 정점, 간선 

graph=[ [] for _ in range(n+1) ]
for i in range(e): 
  a,b,c = map(int,input().split())
  graph[a].append((b,c))
  graph[b].append((a,c))

v1, v2 = map(int,input().split())

def dij(start):
  q = [] 
  heapq.heappush(q,(0,start))
  dist = [1e9]*(n+1)
  dist[start]=0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now] < d : continue 

    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q, (cost,i[0]))
  return dist 


dist_1 = dij(1)
dist_v1 = dij(v1)
dist_v2 = dij(v2)

answer = min( dist_1[v1]+dist_v1[v2]+dist_v2[n], 
  dist_1[v2]+ dist_v2[v1]+dist_v1[n])

if answer >= 1e9 : 
  print(-1)
else : 
  print(answer)

주의사항 ) 

1. 양방향 그래프 => graph 에 추가할 때 앞 뒤로 다 해주기 

2. v1, v2 는 지나는 순서가 정해진 것은 x => 경우의 수 2개로 나누어서 더 작은 것으로 선택하기 

www.acmicpc.net/problem/1916

import heapq
import sys
input = sys.stdin.readline 

n = int(input()) # 도시 
m = int(input()) # 버스 

graph = [ [] for _ in range(n+1)]
for i in range(m):
  s,e,c = map(int,input().split())
  graph[s].append((e,c)) # 도착, 비용 

s, e = map(int,input().split()) # 출발 도착 

def dij(start):
  q = []
  dist = [1e9]*(n+1)
  heapq.heappush(q, (0,start) )
  dist[start]=0

  while q : 
    d, now = heapq.heappop(q)

    if dist[now]< d : continue 

    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q, (cost,i[0]))

  return dist 

result = dij(s)
print(result[e])

기본 다익스트라 구현법 사용!