[백준] 1916번 최소비용 구하기
문제 링크
https://www.acmicpc.net/problem/1916
문제 설명
- start 에서 end 까지 가는 최단거리 출력
풀이
- 다익스트라 알고리즘을 자꾸 까먹어서 다시 한 번 풀어봤다
- start 거리 0, 큐에 푸시
- 반복
- 인접 노드 순회
- 작으면 갱신, 푸시
코드
import heapq, sys
def init():
ipt = sys.stdin.readline
n = int(ipt())
m = int(ipt())
adj_list = [[] for _ in range(n + 1)]
for _ in range(m):
s, e, c = map(int, ipt().split())
adj_list[s].append((e, c))
start, end = map(int, ipt().split())
return n, start, end, adj_list
def dijkstra():
dist = [float('inf')] * (n+1)
dist[start] = 0
q = [(0, start)]
while q:
cd, cn = heapq.heappop(q)
for nn, cost in adj_list[cn]:
nd = cd + cost
if dist[nn] > nd:
dist[nn] = nd
heapq.heappush(q, (nd, nn))
return dist[end]
n, start, end, adj_list = init()
print(dijkstra())
Author And Source
이 문제에 관하여([백준] 1916번 최소비용 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-1916번-최소비용-구하기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 다익스트라 알고리즘을 자꾸 까먹어서 다시 한 번 풀어봤다
- start 거리 0, 큐에 푸시
- 반복
- 인접 노드 순회
- 작으면 갱신, 푸시
- 인접 노드 순회
코드
import heapq, sys
def init():
ipt = sys.stdin.readline
n = int(ipt())
m = int(ipt())
adj_list = [[] for _ in range(n + 1)]
for _ in range(m):
s, e, c = map(int, ipt().split())
adj_list[s].append((e, c))
start, end = map(int, ipt().split())
return n, start, end, adj_list
def dijkstra():
dist = [float('inf')] * (n+1)
dist[start] = 0
q = [(0, start)]
while q:
cd, cn = heapq.heappop(q)
for nn, cost in adj_list[cn]:
nd = cd + cost
if dist[nn] > nd:
dist[nn] = nd
heapq.heappush(q, (nd, nn))
return dist[end]
n, start, end, adj_list = init()
print(dijkstra())
Author And Source
이 문제에 관하여([백준] 1916번 최소비용 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-1916번-최소비용-구하기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import heapq, sys
def init():
ipt = sys.stdin.readline
n = int(ipt())
m = int(ipt())
adj_list = [[] for _ in range(n + 1)]
for _ in range(m):
s, e, c = map(int, ipt().split())
adj_list[s].append((e, c))
start, end = map(int, ipt().split())
return n, start, end, adj_list
def dijkstra():
dist = [float('inf')] * (n+1)
dist[start] = 0
q = [(0, start)]
while q:
cd, cn = heapq.heappop(q)
for nn, cost in adj_list[cn]:
nd = cd + cost
if dist[nn] > nd:
dist[nn] = nd
heapq.heappush(q, (nd, nn))
return dist[end]
n, start, end, adj_list = init()
print(dijkstra())
Author And Source
이 문제에 관하여([백준] 1916번 최소비용 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-1916번-최소비용-구하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)