728x90
반응형
SMALL
백준 저지에서 최단경로를 파이썬을 통해 풀어 보았다.
https://www.acmicpc.net/problem/1753
1753번 최단경로
문제
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
설명
아주 기본적인 다익스트라 문제이다. 지난 포스팅에 설명한 다익스트라를 그대로 적용하면 된다.
코드
#1753번 최단경로.py
import heapq
import sys
import sys
input = sys.stdin.readline
def dijkstra(start) :
q=[]
root[start]=0 #자기 자신에게 가는 것은 0
heapq.heappush(q,(0,start)) #힙에 비용, 출발 노드 저장
while q :
cost, now = heapq.heappop(q) # 가장 작은 가중치를 가진 노드 선택
if root[now] < cost : #선택한 노드의 가중치가 이미 저장된 가중치보다 크면 실행x
continue
for next in graph[now] :
next_cost = cost+next[1] #현재 노드에서 다음 노드까지 가중치 계산
if next_cost < root[next[0]] : #가중치가 더 작으면
root[next[0]]=next_cost #갱신
heapq.heappush(q,(next_cost,next[0]))#heap에 추가
V,E = map(int,input().split())
k = int(input())
graph = [[]for _ in range(V+1)]
for i in range(E) :
u,v,w = map(int,input().split())
graph[u].append([v,w])
root = [int(1e9)]*(V+1)
dijkstra(k)
for i in range(1,V+1) :
if root[i] == int(1e9) :
print("INF")
else :
print(root[i])
728x90
반응형
SMALL
'Problem Solving > 백준BOJ' 카테고리의 다른 글
[백준BOJ] 16505번 별.java (0) | 2021.08.02 |
---|---|
[백준BOJ] 1991번 트리 순회.py (0) | 2021.07.29 |
[백준BOJ] 15666번 N과 M(12).py (0) | 2021.07.27 |
[백준BOJ] 1181번 단어 정렬.java (0) | 2021.07.26 |
[백준BOJ] 11779번 최소비용 구하기2.py (0) | 2021.07.25 |