문제 링크
https://www.acmicpc.net/problem/11779
11779번: 최소비용 구하기 2
첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스
www.acmicpc.net
풀이
- 다익스트라 사용하여 최소 비용 구하는 문제
- distance에는 최소비용
path에는 경로 저장
import sys, heapq
input = sys.stdin.readline
n = int(input())
m = int(input())
INF = int(1e9)
graph = [ [] for _ in range(n+1) ]
# 최단 거리저장
distance = [INF] * (n+1)
# 경로 저장
path = [ [] for _ in range(n+1) ]
for _ in range(m):
a,b,c = map(int,input().split())
graph[a].append((b,c))
start,end = map(int,input().split())
def dijkstra(start):
q = []
distance[start] = 0
heapq.heappush(q, (0,start))
path[start].append(start)
while q:
dist, now = heapq.heappop(q)
# 이미 처리된 경우
if distance[now] < dist :
continue
for i in graph[now]:
cost = dist + i[1]
# 갱신
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q,(cost,i[0]))
# path 갱신 : now까지의 경로 + 현재 위치
path[i[0]] = []
for p in path[now]:
path[i[0]].append(p)
path[i[0]].append(i[0])
dijkstra(start)
print(distance[end])
print(len(path[end]))
print(*path[end])
'개발 > algorithm' 카테고리의 다른 글
[프로그래머스][level2] 행렬 테두리 회전하기 - python (0) | 2022.03.25 |
---|---|
[백준 2263번] 트리의 순회 - python (0) | 2022.03.18 |
[백준 1918번] 후위 표기식 - python (0) | 2022.03.18 |
[백준 5639번] 이진 검색 트리 - python (0) | 2022.03.18 |
[백준 2448번] 별 찍기 - 11 - python (0) | 2022.03.18 |