Algorithm/Graph
[백준] 1916번 최소비용 구하기 (Python)
잘될거야아마두
2021. 3. 2. 22:51
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
다익스트라 문제
특정 출발점으로부터 특정 도착점까지의 최소비용을 묻고 있기 때문에, 하나의 출발점에 대한 비용행렬을 만들면 된다!! (1차원 행렬)
📢 주의해야 하는 점
- 방향 그래프이다!! (처음에 무방향 그래프라고 생각했다가 틀렸다...😥)
- 한 노드로부터 다른 노드로 가는 간선이 여러 개일 수 있다!!
예를 들어, 입력이 다음과 같이 주어지면,
1 2 3
1 2 10
비용이 적은 첫번째 간선을 선택하도록 해야한다.
다익스트라와 플로이드-와샬의 차이점은 아래 포스트를 참고
2021/02/25 - [Algorithm/Graph] - [프로그래머스] 합승 택시 요금 (Python)
[프로그래머스] 합승 택시 요금 (Python)
코딩테스트 연습 - 합승 택시 요금 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3..
summa-cum-laude.tistory.com
import sys
from math import inf
from heapq import heappush, heappop
read = lambda: sys.stdin.readline().strip()
def dijkstra(graph, start):
dist = [inf for _ in range(n)]
dist[start] = 0
q = []
heappush(q, [0, start])
while q:
cur_dist, cur_node = heappop(q)
if dist[cur_node] >= cur_dist:
for i in range(n):
new_dist = cur_dist + graph[cur_node][i]
if new_dist < dist[i]:
dist[i] = new_dist
heappush(q, [new_dist, i])
return dist
n = int(read())
m = int(read())
costs = [[inf] * n for _ in range(n)]
for _ in range(m):
u, v, c = map(int, read().split())
if costs[u - 1][v - 1] != inf and costs[u - 1][v - 1] <= c:
continue
costs[u - 1][v - 1] = c
dep, arr = map(int, read().split())
dep, arr = dep - 1, arr - 1
result = dijkstra(costs, dep)
print(result[arr])