728x90
|
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
# '''
# 다익스트라
# 예쩨진짜..
# '''
#
# def dijkstra(start):
# # 시작점 설정 ( 가중치 0으로 )
# u = start # 가중치가 최소인 정점
# dist[u] = 0
# ################################################같다
# # 정점의 갯수만큼 반복
# for i in range(V):
# # 가중치 최소값 찾기
# min = 987654321
# for v in range(V):
# if visited[v] == 0 and min > dist[v]:
# min = dist[v]
# u = v # 최소값
# ################################################같다
# # 방문처리
# visited[u] = 1
#
#
# # 인접 정점에 업데이트하기
# for v in range(V):
# # 인접하고 방문 안하고 간선의 가중치 정점의 가중치를 비교
# # if adj[u][v] != 0 and visited[v] == 0 and adj[u][v] < dist[v]:
# if adj[u][v] != 0 and visited[v] == 0 and dist[u] + adj[u][v] < dist[v]:
# #########################################-dist + 추가함------------------##
# #print(dist[u])
# #print(adj[u][v])
# dist[v] = dist[u] + adj[u][v] # 가중치
# # -dist + 추가함--------------##
#
# T= int(input())
# for tc in range(1,T+1):
# V, E = map(int, input().split()) # 정점수, 간선수
# adj = [[0]* (V) for _ in range(V)] # 인접 행렬/
# dist = [987654321] * (V) # 가중치
#
# visited = [0] * (V) # 방문체크
# #입력
#
# for i in range(E):
# edge = list(map(int, input().split())) # 출발, 도착, 가중치
# adj[edge[0]][edge[1]] = edge[2]
# adj[edge[1]][edge[0]] = edge[2]
#
# dijkstra(0)
# print(dist)
'''
다익스트라
3
1
2 3
0 1 1
0 2 -6
1 2 1
4 7
0 1 9
0 2 3
0 3 7
1 4 2
2 3 8
2 4 1
3 4 8
4 6
0 1 10
0 2 7
1 4 2
2 3 10
2 4 3
3 4 10
'''
def dijkstra(start):
# 시작점 설정 ( 가중치 0으로 )
u = start # 가중치가 최소인 정점
dist[u] = 0
################################################같다
# 정점의 갯수만큼 반복
for i in range(V+1):
# 가중치 최소값 찾기
min = 987654321
for v in range(V+1):
if visited[v] == 0 and min > dist[v]:
min = dist[v]
u = v # 최소값
################################################같다
# 방문처리
visited[u] = 1
# 인접 정점에 업데이트하기
for v in range(V+1):
# 인접하고 방문 안하고 간선의 가중치 정점의 가중치를 비교
# if adj[u][v] != 0 and visited[v] == 0 and adj[u][v] < dist[v]:
if adj[u][v] != 0 and visited[v] == 0 and dist[u] + adj[u][v] < dist[v]:
#########################################-dist + 추가함------------------##
#print(dist[u])
#print(adj[u][v])
dist[v] = dist[u] + adj[u][v] # 가중치
# -dist + 추가함--------------##
T= int(input())
for tc in range(1,T+1):
V, E = map(int, input().split()) # 정점수, 간선수
adj = [[0]* (V+1) for _ in range(V+1)] # 인접 행렬/
dist = [987654321] * (V+1) # 가중치
visited = [0] * (V+1) # 방문체크
#입력
for i in range(E):
edge = list(map(int, input().split())) # 출발, 도착, 가중치
adj[edge[0]][edge[1]] = edge[2]
dijkstra(0)
print("#{} {}".format(tc, dist[-1]))
|
cs |
for i in range(E):
edge = list(map(int, input().split())) # 출발, 도착, 가중치
adj[edge[0]][edge[1]] = edge[2]
adj[edge[1]][edge[0]] = edge[2]
추가적으로 이부분에서 방향이 없는 문제라면 가중치 값을 양방향으로 대입시켜주면 됩니다.
728x90
'알고리즘 > SWAE' 카테고리의 다른 글
| [python] 2072. 홀수만 더하기 D1 (0) | 2022.08.10 |
|---|---|
| 1486. 장훈이의 높은 선반 (0) | 2021.04.20 |
| 2819. 격자판의 숫자 이어붙이기 (0) | 2021.04.17 |
| 최소합 (0) | 2021.04.14 |
| 2635. 수 이어가기. (0) | 2021.04.11 |