(프로그래머의) 연결 제도 – Python

문제 설명

n개의 섬 사이에 다리를 건설하는 비용이 주어지면 모든 섬을 최소 비용으로 서로 통과할 수 있도록 만드는 데 필요한 최소 비용을 반환하도록 솔루션을 완성하십시오.

다리를 여러 번 건너더라도 도달할 수 있는 한 통행 가능한 것으로 간주됩니다.

예를 들어 A섬과 B섬 사이, B섬과 C섬 사이에 다리가 있다면 A섬과 C섬은 서로 통행이 가능하다.

제한

• 섬의 수 n은 1보다 크거나 같고 100보다 작거나 같습니다.
  
  
• 비용의 길이 ((n-1) * n) / 2 이하.
• 모든 i의 경우, cost(i)(0) 및 cost(i) (1)에는 다리가 연결하는 두 개의 섬 수가 포함되고, cost(i) (2)에는 이 두 개의 섬을 연결하는 다리가 포함됩니다.
  
  공사비입니다.
  
  
• 동일한 연결은 두 번 제공되지 않습니다.
  
  또한 순서가 뒤바뀐 경우에도 동일한 연결이 표시됩니다.
  
  즉, 0과 1 사이를 연결하는 비용이 주어지면 1과 0의 비용은 주어지지 않는다.
  
  
• 모든 섬 사이의 다리 건설 비용은 주어지지 않습니다.
  
  이 경우 두 섬 사이의 건설은 불가능한 것으로 간주됩니다.
  
  
• 도달할 수 없는 섬은 주어지지 않습니다.
  
  

I/O 예시

I/O 예제 설명

암호

def solution(n, costs):
    ans = 0
    costs.sort(key = lambda x: x(2))
    routes = set((costs(0)(0)))
    while len(routes) < n:
        for i, cost in enumerate(costs):
            if cost(0) in routes and cost(1) in routes:
                continue
            if cost(0) in routes or cost(1) in routes:
                routes.update((cost(0), cost(1)))
                ans += cost(2)
                costs(i) = (-1, -1, -1)
                break
    return ans