728x90
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
분석
[1753번] 최단경로 구하기 (다익스트라, 우선순위큐, 힙)
다익스트라 음수간선 X S 시작점부터 다른 모든 노드로 가는 최단거리 구하는 알고리즘 기출 : 음수간선이 없는데 시작점이 있고 최단거리 구하는 문제 원리 최단거리를 구할 노드에서 시작하여
karla.tistory.com
그래프 최단거리 알고리즘 정리 및 비교 (다익스트라, 벨만-포드, 플로이드-워셜)
다익스트라 벨만-포드 플로이드-워셜 시작 노드 (시작점) O O X (모든 노드) 음수 간선 X O O 시간 복잡도 O(ElogV) O(EV) O(V³) 1. 다익스트라 출발 노드와 모든 노드 간의 최단 거리 탐색 음수간선 X S 시
karla.tistory.com
풀이
import sys
from queue import PriorityQueue
input=sys.stdin.readline
# 도시개수
n=int(input())
#버스개수
m=int(input())
# 최단거리 리스트
d=[sys.maxsize] * (n+1)
# 방문 배열
visited=[False] * (n+1)
# 인접 리스트
graph=[[] for _ in range(n+1)]
for i in range(m):
# 출발도시, 도착도시, 버스비용
u,v,w=map(int, input().split())
graph[u].append((v,w))
start,end=map(int, input().split())
# 다익스트라
def dijkstra(s,e):
q=PriorityQueue()
# 출발 노드는 우선순위 큐에 넣고 시작
q.put((0,s)) # s를 시작점으로 설정
# 우선순위에 데이터를 최단거리 노드순으로 삽입
# 거리 리스트에 출발 노드의 값을 0으로 설정
d[s]=0
while q.qsize() > 0:
# 우선순위 큐에서 노드 가져오기
nowNode = q.get()
# print(nowNode)
now=nowNode[1]
# 현재 선택 노드 방문 여부 확인
if visited[now]:
continue
# 현재 노드 방문 처리
visited[now] = True
for i in graph[now]:
next = i[0]
value = i[1]
# 타깃노드 방문전, 타깃노드 최단거리 > 현재선택노드 최단거리+비용
if not visited[next] and d[next]> d[now]+value:
# 타깃노드 최단거리 업데이트
d[next]=d[now]+value
# 우선순위 큐에 타깃노드 추가
q.put((d[next], next))
# 종료 인덱스 최종거리 리턴
return d[e]
print(dijkstra(start,end))
728x90