[๋ฐฑ์ค-1753] ์ต๋จ๊ฒฝ๋ก / Python
๐ Problem Solving/Baekjoon
https://www.acmicpc.net/problem/1753
1753๋ฒ: ์ต๋จ๊ฒฝ๋ก
์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ V์ ๊ฐ์ ์ ๊ฐ์ E๊ฐ ์ฃผ์ด์ง๋ค. (1≤V≤20,000, 1≤E≤300,000) ๋ชจ๋ ์ ์ ์๋ 1๋ถํฐ V๊น์ง ๋ฒํธ๊ฐ ๋งค๊ฒจ์ ธ ์๋ค๊ณ ๊ฐ์ ํ๋ค. ๋์งธ ์ค์๋ ์์ ์ ์ ์ ๋ฒํธ K(1≤K≤V)๊ฐ ์ฃผ์ด์ง๋ค.
www.acmicpc.net
import sys
import heapq
INF = int(1e9)
V, E = map(int, sys.stdin.readline().split())
k = int(sys.stdin.readline())
graph = [[] for _ in range(V + 1)]
distance = [INF] * (V + E)
for _ in range(E):
u, v, w = map(int, input().split())
graph[u].append((v, w))
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(k)
for i in range(1, V + 1):
if distance[i] == INF:
print("INF")
else:
print(distance[i])
ํด์ค
์ด์ ์ด์ทจ์ฝ ์ฑ ์์ ๋ณต์ตํ๋ ๋ค์ต์คํธ๋ผ ๋ฌธ์ ์ ๊ฐ๋ค. ์ด์ ๋ณต์ตํ ๋๋ถ์ ์์ํ๊ฒ ํด๊ฒฐํ๋ค !๐
'๐ Problem Solving > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-13549] ์จ๋ฐ๊ผญ์ง 3 / Python (0) | 2021.05.21 |
---|---|
[๋ฐฑ์ค-1916] ์ต์๋น์ฉ ๊ตฌํ๊ธฐ / Python (0) | 2021.05.20 |
[๋ฐฑ์ค-1912] ์ฐ์ํฉ / Python (0) | 2021.05.19 |
[๋ฐฑ์ค-11053] ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด / Python (0) | 2021.05.19 |
[๋ฐฑ์ค-1149] RGB๊ฑฐ๋ฆฌ / Python (0) | 2021.05.19 |