[백준 10217] KCM Travel - Python(파이썬)
다익스트라와 냅색을 활용한 코드 from heapq import heappop, heappush import sys def solution(): check = [[float('inf')] * (M+1) for _ in range(N+1)] temp = [(0, 0, 1)] while temp: # d: 거리, c: 비용, idx: 해당 인덱스 d, c, idx = heappop(temp) if check[idx][c] < d: continue # 원하는 인덱스면, 해당 거리 리턴! if idx == N: return d # k: 해당 인덱스, l: 비용, m: 거리 for k, l, m in dist[idx]: l += c m += d # 합 비용이 예산 초과거나 합 거리가 check의 거리 이상일 경우..
2021. 3. 27.
[백준 9370] 미확인 도착지 - Python(파이썬)
from heapq import heappush, heappop import sys def solution(x): check = [100000000] * (n+1) check[x] = 0 my_heap = [(0, x)] while my_heap: k, l = heappop(my_heap) for o, p in dist[l].items(): p += k if check[o] > p: check[o] = p heappush(my_heap, (p, o)) return check T = int(sys.stdin.readline().strip()) for tc in range(T): n, m, t = map(int, sys.stdin.readline().split()) s, g, h = map(int, sys...
2021. 3. 11.
[백준 1504] 특정한 최단 경로 - Python(파이썬)
from heapq import heappush, heappop import sys def solution(s): check = [float('inf')] * (N + 1) check[s] = 0 temp = [(0, s)] while temp: x, y = heappop(temp) if check[y] >= x: for n, m in dist[y]: m += x if check[n] > m: check[n] = m heappush(temp, (m, n)) return check N, E = map(int, sys.stdin.readline().split()) dist = {i: [] for i in range(N + 1)} for e in range(E): a, b, c = map(int, sys.st..
2021. 3. 11.