[伯俊23743]密室脱出
1.問題の説明
密室脱出
2.問題分析
非常口を0番にして接続するとMSTを救う問題になります.
3.私の回答 import sys
import heapq
n, m = map(int, sys.stdin.readline().rstrip().split())
parents = [i for i in range(n+1)]
pq = []
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
heapq.heappush(pq, [c, a, b])
for node, cost in enumerate(list(map(int, sys.stdin.readline().rstrip().split())), start=1):
heapq.heappush(pq, [cost, 0, node])
# 비상탈출구를 하나의 노드로 생각한다.
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1 ,root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
total = 0
edge_cnt = 0
while pq:
cost, node1, node2 = heapq.heappop(pq)
if union(node1, node2):
total += cost
edge_cnt += 1
if edge_cnt == n: break
# n개의 노드 + 비상탈출구 노드 = n+1-1, 즉 n개의 간선이 추가되면 MST를 구할 수 있다.
print(total)
Reference
この問題について([伯俊23743]密室脱出), 我々は、より多くの情報をここで見つけました
https://velog.io/@j_aion/백준-23743-방탈출
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
非常口を0番にして接続するとMSTを救う問題になります.
3.私の回答 import sys
import heapq
n, m = map(int, sys.stdin.readline().rstrip().split())
parents = [i for i in range(n+1)]
pq = []
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
heapq.heappush(pq, [c, a, b])
for node, cost in enumerate(list(map(int, sys.stdin.readline().rstrip().split())), start=1):
heapq.heappush(pq, [cost, 0, node])
# 비상탈출구를 하나의 노드로 생각한다.
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1 ,root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
total = 0
edge_cnt = 0
while pq:
cost, node1, node2 = heapq.heappop(pq)
if union(node1, node2):
total += cost
edge_cnt += 1
if edge_cnt == n: break
# n개의 노드 + 비상탈출구 노드 = n+1-1, 즉 n개의 간선이 추가되면 MST를 구할 수 있다.
print(total)
Reference
この問題について([伯俊23743]密室脱出), 我々は、より多くの情報をここで見つけました
https://velog.io/@j_aion/백준-23743-방탈출
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import sys
import heapq
n, m = map(int, sys.stdin.readline().rstrip().split())
parents = [i for i in range(n+1)]
pq = []
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
heapq.heappush(pq, [c, a, b])
for node, cost in enumerate(list(map(int, sys.stdin.readline().rstrip().split())), start=1):
heapq.heappush(pq, [cost, 0, node])
# 비상탈출구를 하나의 노드로 생각한다.
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1 ,root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
total = 0
edge_cnt = 0
while pq:
cost, node1, node2 = heapq.heappop(pq)
if union(node1, node2):
total += cost
edge_cnt += 1
if edge_cnt == n: break
# n개의 노드 + 비상탈출구 노드 = n+1-1, 즉 n개의 간선이 추가되면 MST를 구할 수 있다.
print(total)
Reference
この問題について([伯俊23743]密室脱出), 我々は、より多くの情報をここで見つけました https://velog.io/@j_aion/백준-23743-방탈출テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol