💡문제접근
- 발전소들을 Union시켜서 하나의 집합으로 만들어준다.
💡코드(메모리 : 49836KB, 시간 : 396ms)
import sys
input = sys.stdin.readline
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def unions_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
N, M, K = map(int, input().strip().split())
parent = [0] * (N+1)
edges = []
result = 0
factory = list(map(int, input().strip().split()))
for _ in range(M):
u, v, w = map(int, input().strip().split())
edges.append([w, u, v])
edges.sort()
for i in range(1, N+1):
if i in factory:
continue
else:
parent[i] = i
for edge in edges:
cost, u, v = edge
if find_parent(parent, u) != find_parent(parent, v):
unions_parent(parent, u, v)
result += cost
print(result)
💡소요시간 : 34m