문제
https://www.acmicpc.net/problem/5972
풀이
택배 배송 문제, 여물을 헛간인 1에서 헛간 N으로 배달하는 것은 여러가지 그래프를 활용하여 풀 수 있다.
그중 가는 길의 길이는 고려하지 않으므로, 다익스트라를 활용하여 풀 수 있다.
입력에 대한 그래프를 구성하는 과정에서, 해당 문제는 간선에 대해 방향을 따지지 않는 무향 그래프 이므로, 입력 시에 양쪽 출력 노드에 대해 값을 추가해주어야 한다.
코드
import heapq
INF = int(1e9)
N,M = map(int, input().split())
graph = [[] * (N+1) for _ in range(N+1)]
distance = [INF] * (N+1)
for _ in range(M):
a,b,c = map(int, input().split())
graph[a].append((b,c))
graph[b].append((a,c))
def dijkstra(start):
q = []
heapq.heappush(q, (0,start))
distance[start] = 0
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]))
dijkstra(1)
print(distance[N])
'Koala - 12기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/python] 5972번: 택배 배송 (1) | 2023.11.13 |
---|---|
[백준/python3] 4485번 : 녹색 옷을 입은 애가 젤다지? (0) | 2023.11.12 |
[백준|파이썬] Игра (2) | 2023.11.09 |
[백준/phthon3] 9372번: 상근이의 여행 (0) | 2023.11.06 |
[백준/Python] 7576번 : 토마토 (0) | 2023.11.06 |