🐸 문제 정보
🤖 알고리즘
다익스트라
⏱️ 풀이 시간
30.05m
📝 풀이
최근에 공부한 최단거리 포스팅을 읽어보면 쉽게 풀 수 있는 문제였다.
모든 거리 지점을 노드라고 생각하고, 각 지점에서 다음 지점까지 가중치 1씩을 기본으로 설정했다.
그리고 지름길이 있는 부분에 간선을 추가하여 다익스트라를 돌리면 되는 문제였다.
뭔가 뿌듯했다.. 나 이제 최단 경로 찾기 잘할수있숴
🧑💻 나의 답
# pypy3
import sys, heapq
input = sys.stdin.readline
INF = sys.maxsize
n, d = list(map(int, input().rstrip().split()))
graph = [[(i + 1, 1)] if i < d else [] for i in range(d + 1)]
distance = [INF] * (d + 1)
for _ in range(n):
u, v, m = list(map(int, input().rstrip().split()))
if u > d: continue
if v > d: continue
graph[u].append((v, m))
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 node in graph[now]:
if dist + node[1] < distance[node[0]]:
distance[node[0]] = dist + node[1]
heapq.heappush(q, (dist + node[1], node[0]))
dijkstra(0)
print(distance[d])
'PS > 문제풀이' 카테고리의 다른 글
백준 1205 등수 구하기 Python (0) | 2024.01.20 |
---|---|
백준 13549 숨바꼭질 3 (0) | 2024.01.17 |
백준 20310 타노스 Python (0) | 2024.01.17 |
백준 19941 햄버거 분배 Python (0) | 2024.01.17 |
백준 1515 수 이어 쓰기 Python (0) | 2024.01.16 |