틀렸던 내 풀이
|
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
|
from heapq import heappush, heappop
n, m, r = map(int, input().split())
item_value = [0] + list(map(int, input().split()))
data = [[] for _ in range(n + 1)]
INF = int(1e9)
for _ in range(r):
a, b, c = map(int, input().split())
data[a].append((b, c))
data[b].append((a, c))
def dijkstra(start):
q = []
distance = [INF for _ in range(n+1)]
heappush(q, (0, start))
sum_data = item_value[start]
distance[start] = 0
visited = [False for _ in range(n+1)]
visited[start] = True
while q:
dis, node = heappop(q)
for i in data[node]:
cost = dis + i[1]
if cost < distance[i[0]] and cost <= m:
distance[i[0]] = cost
heappush(q, (cost, i[0]))
sum_data += item_value[i[0]]
return sum_data
def solved():
result = []
for i in range(1, n+1):
result.append(dijkstra(i))
print(max(result))
solved()
|
cs |
맞은 내 풀이
|
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
|
from heapq import heappush, heappop
n, m, r = map(int, input().split())
item_value = [0] + list(map(int, input().split()))
data = [[] for _ in range(n + 1)]
INF = int(1e9)
for _ in range(r):
a, b, c = map(int, input().split())
data[a].append((b, c))
data[b].append((a, c))
def dijkstra(start):
q = []
distance = [INF for _ in range(n + 1)]
heappush(q, (0, start))
distance[start] = 0
while q:
dis, node = heappop(q)
for i in data[node]:
cost = dis + i[1]
if cost < distance[i[0]] and cost <= m:
distance[i[0]] = cost
heappush(q, (cost, i[0]))
return distance
def solved():
max_value = -INF
for i in range(1, n + 1):
sum_data = 0
result = dijkstra(i)
for j in range(1, n+1):
if result[j] <= m:
sum_data += item_value[j]
max_value = max(max_value, sum_data)
print(max_value)
solved()
|
cs |
첫 번쨰 코드와 두 번째 코드의 차이점이 구체적으로 무엇일까?
첫 번째는