[๋ฐฑ์ค-5972] ํ๋ฐฐ ๋ฐฐ์ก / Python
๐ Problem Solving/Baekjoon
5972๋ฒ: ํ๋ฐฐ ๋ฐฐ์ก
๋๋ถ ํ์๋ ๋๋ถ ์ฐฌํ์ด์๊ฒ ํ๋ฐฐ๋ฅผ ๋ฐฐ๋ฌํด์ค์ผ ํฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ ์ง๊ธ, ๊ฐ ์ค๋น๋ฅผ ํ๊ณ ์์ต๋๋ค. ํํ๋กญ๊ฒ ๊ฐ๋ ค๋ฉด ๊ฐ๋ ๊ธธ์ ๋ง๋๋ ๋ชจ๋ ์๋ค์๊ฒ ๋ง์๋ ์ฌ๋ฌผ์ ์ค์ผ ํฉ๋๋ค. ๋ฌผ๋ก ํ์๋
www.acmicpc.net
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
graph = [[] 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[-1])
ํด์ค
์ต๋จ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ(๋ค์ต์คํธ๋ผ)์ผ๋ก ํด๊ฒฐํ ์ ์์๋ ๋ฌธ์ ์๋ค.
'๐ Problem Solving > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-14497] ์ฃผ๋์ ๋(้ฃ) / Python (0) | 2021.07.02 |
---|---|
[๋ฐฑ์ค-18405] ๊ฒฝ์์ ์ ์ผ / Python (0) | 2021.07.02 |
[๋ฐฑ์ค-6118] ์จ๋ฐ๊ผญ์ง / Python (0) | 2021.07.02 |
[๋ฐฑ์ค-1743] ์์๋ฌผ ํผํ๊ธฐ / Python (0) | 2021.07.02 |
[๋ฐฑ์ค-1926] ๊ทธ๋ฆผ / Python (0) | 2021.07.01 |