문제
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
처음 작성한 코드
import sys
from collections import deque
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
result = [sys.maxsize] * (N+1)
arr = {i+1:[] for i in range(N)}
for _ in range(M):
u, v, w = map(int, sys.stdin.readline().split())
arr[u].append([v,w])
s , e = map(int, sys.stdin.readline().split())
queue = deque()
result[s] = 0
queue.append(s)
while queue:
u = queue.popleft()
for v, w in arr[u]:
if result[v] > result[u] + w:
result[v] = result[u] + w
queue.append(v)
print(result[e])
깨달은 점
- 단순한 다익스트라를 이용한 문제였다. 한 점에서 다른 점까지 최소거리를 구할 때 다익스트라를 쓰면 되는 것 같다. 손에 익으니까 재밌다 ㅋ ㅋ
'Baekjoon' 카테고리의 다른 글
| [백준 1261] 알고스팟 (0) | 2021.03.17 |
|---|---|
| [백준 1753] 최단경로 (0) | 2021.03.16 |
| [백준 1446] 지름길 (0) | 2021.03.16 |
| [백준 4963] 섬의 개수 (0) | 2021.03.13 |
| [백준 2170] 선 긋기 (0) | 2021.03.09 |