[๋ฐฑ์ค-1916] ์ต์๋น์ฉ ๊ตฌํ๊ธฐ / Python
๐ Problem Solving/Baekjoon
1916๋ฒ: ์ต์๋น์ฉ ๊ตฌํ๊ธฐ
์ฒซ์งธ ์ค์ ๋์์ ๊ฐ์ N(1 ≤ N ≤ 1,000)์ด ์ฃผ์ด์ง๊ณ ๋์งธ ์ค์๋ ๋ฒ์ค์ ๊ฐ์ M(1 ≤ M ≤ 100,000)์ด ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ์ ์งธ ์ค๋ถํฐ M+2์ค๊น์ง ๋ค์๊ณผ ๊ฐ์ ๋ฒ์ค์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ๋จผ์ ์ฒ์์๋ ๊ทธ
www.acmicpc.net
import sys
import heapq
INF = int(1e9)
n = int(input())
m = int(input())
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))
start, end = map(int, input().split())
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(start)
print(distance[end])
ํด์ค
๊ธฐ๋ณธ์ ์ธ ๋ค์ต์คํธ๋ผ ๋ฌธ์ !๐
'๐ Problem Solving > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-2583] ์์ญ ๊ตฌํ๊ธฐ / Python (0) | 2021.05.22 |
---|---|
[๋ฐฑ์ค-13549] ์จ๋ฐ๊ผญ์ง 3 / Python (0) | 2021.05.21 |
[๋ฐฑ์ค-1753] ์ต๋จ๊ฒฝ๋ก / Python (0) | 2021.05.20 |
[๋ฐฑ์ค-1912] ์ฐ์ํฉ / Python (0) | 2021.05.19 |
[๋ฐฑ์ค-11053] ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด / Python (0) | 2021.05.19 |