n개의 도시와 도시를 연결하는 m개의 도로가 있다고 가정합니다. 시민들은 상품을 살 수 있는 시장이 필요합니다. 이제 도시에는 시장이 없고 도시 사이의 도로가 건설 중입니다. (i) 도시에 시장이 있는 경우 두 도시 사이에 양방향 도로를 건설할 수 있습니다. (ii) 시장이 있는 도로를 통해 도시를 방문할 수 있습니다. 도로 건설 비용은 x이고 시장 건설 비용은 y이며 주어진다. 우리는 각 도시의 시민들에게 시장에 대한 접근을 제공하기 위한 최소 비용을 찾아야 합니다. 'cities' 배열에는 도로로 연결할 수 있는 도시에 대한 정보가 포함됩니다.
따라서 입력이 n =4, m =3, x =1, y =2, 도시 =[[1, 2], [2, 3], [3, 4]]인 경우 출력은 다음과 같습니다. 4.
여기에서 4개의 도시 1, 2, 3, 4를 볼 수 있습니다. t 도시 1에 시장이 건설되고 (1, 4)와 (1,3) 사이에 두 개의 도로가 더 건설되면 총 비용은 2 + 1이 됩니다. + 1 =4. 최소 비용입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- x <=y이면
- n * x를 반환
- 그렇지 않으면
- adj_list :=목록을 요소로 포함하는 지도
- 도시의 각 도시에 대해 다음을 수행합니다.
- city1 :=도시[0]
- city2 :=도시[1]
- adj_list[city1] 끝에 city2 삽입
- adj_list[city2] 끝에 city1 삽입
- temp :=True 값으로 초기화된 크기(n + 1)의 새 목록
- 값:=0
- dq :=이중 종료 대기열
- 1 ~ n + 1 범위의 cur에 대해 다음을 수행합니다.
- temp[cur]가 0이 아니면
- 값 :=값 + x
- dq의 가장 오른쪽 끝에 cur 삽입
- temp[cur] :=거짓
- dq가 비어 있지 않은 동안 수행
- 각 i adj_list[dq의 가장 왼쪽에서 추출된 요소]에 대해 다음을 수행합니다.
- temp[i]가 0이 아니면
- dq의 가장 오른쪽 끝에 i 삽입
- temp[i] :=거짓
- 값 :=값 + y
- temp[i]가 0이 아니면
- temp[cur]가 0이 아니면
- 반환 값
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
컬렉션에서 import defaultdict, dequedef solve(n, m, x, y, 도시):if x <=y:return n * x else:adj_list =defaultdict(list) for city in city:city1 =city[0 ] city2 =city[1] adj_list[city1].append(city2) adj_list[city2].append(city1) temp =[True] * (n + 1) 값 =0 dq =deque() in range(1) , n + 1):if temp[cur]:값 +=x dq.append(cur) temp[cur] =False 동안 dq:for i in adj_list[dq.popleft()]:if temp[i]:dq .append(i) temp[i] =거짓 값 +=y 반환 값print(solve(4, 3, 1, 2, [[1, 2], [2, 3], [3, 4]]))입력
4, 3, 2, 1, [[1, 2], [2, 3], [3, 4]]출력
4