forked from ndb796/python-for-coding-test
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path1.py
More file actions
60 lines (54 loc) ยท 2.16 KB
/
1.py
File metadata and controls
60 lines (54 loc) ยท 2.16 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import sys
input = sys.stdin.readline
INF = int(1e9) # ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์
# ๋
ธ๋์ ๊ฐ์, ๊ฐ์ ์ ๊ฐ์๋ฅผ ์
๋ ฅ๋ฐ๊ธฐ
n, m = map(int, input().split())
# ์์ ๋
ธ๋ ๋ฒํธ๋ฅผ ์
๋ ฅ๋ฐ๊ธฐ
start = int(input())
# ๊ฐ ๋
ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋
ธ๋์ ๋ํ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค๊ธฐ
graph = [[] for i in range(n + 1)]
# ๋ฐฉ๋ฌธํ ์ ์ด ์๋์ง ์ฒดํฌํ๋ ๋ชฉ์ ์ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค๊ธฐ
visited = [False] * (n + 1)
# ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ์ ๋ชจ๋ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ
distance = [INF] * (n + 1)
# ๋ชจ๋ ๊ฐ์ ์ ๋ณด๋ฅผ ์
๋ ฅ๋ฐ๊ธฐ
for _ in range(m):
a, b, c = map(int, input().split())
# a๋ฒ ๋
ธ๋์์ b๋ฒ ๋
ธ๋๋ก ๊ฐ๋ ๋น์ฉ์ด c๋ผ๋ ์๋ฏธ
graph[a].append((b, c))
# ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋ ์ค์์, ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋
ธ๋์ ๋ฒํธ๋ฅผ ๋ฐํ
def get_smallest_node():
min_value = INF
index = 0 # ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋
ธ๋(์ธ๋ฑ์ค)
for i in range(1, n + 1):
if distance[i] < min_value and not visited[i]:
min_value = distance[i]
index = i
return index
def dijkstra(start):
# ์์ ๋
ธ๋์ ๋ํด์ ์ด๊ธฐํ
distance[start] = 0
visited[start] = True
for j in graph[start]:
distance[j[0]] = j[1]
# ์์ ๋
ธ๋๋ฅผ ์ ์ธํ ์ ์ฒด n - 1๊ฐ์ ๋
ธ๋์ ๋ํด ๋ฐ๋ณต
for i in range(n - 1):
# ํ์ฌ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋
ธ๋๋ฅผ ๊บผ๋ด์, ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ
now = get_smallest_node()
visited[now] = True
# ํ์ฌ ๋
ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ๋
ธ๋๋ฅผ ํ์ธ
for j in graph[now]:
cost = distance[now] + j[1]
# ํ์ฌ ๋
ธ๋๋ฅผ ๊ฑฐ์ณ์ ๋ค๋ฅธ ๋
ธ๋๋ก ์ด๋ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์ ๊ฒฝ์ฐ
if cost < distance[j[0]]:
distance[j[0]] = cost
# ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ํ
dijkstra(start)
# ๋ชจ๋ ๋
ธ๋๋ก ๊ฐ๊ธฐ ์ํ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ
for i in range(1, n + 1):
# ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ, ๋ฌดํ(INFINITY)์ด๋ผ๊ณ ์ถ๋ ฅ
if distance[i] == INF:
print("INFINITY")
# ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ
else:
print(distance[i])