프로그래밍/HackerRank
[HackerRank][Python3] Roads and Libraries
snoopybox
2018. 7. 22. 17:43
Problem :
https://www.hackerrank.com/challenges/torque-and-development/problem
My Solution :
#!/usr/bin/env python3 def dfs(nodes, node, visited): if visited[node]: return 0 visited[node] = 1 count = 1 for neighbor in nodes[node]: count += dfs(nodes, neighbor, visited) return count def roadsAndLibraries(n, c_lib, c_road, cities): nodes = {i+1: [] for i in range(n)} visited = [0]*(n+1) for u, v in cities: nodes[u].append(v) nodes[v].append(u) cost = 0 for node in nodes: count = dfs(nodes, node, visited) if count: cost += c_lib + (count-1)*min(c_lib, c_road) return cost q = int(input()) for _ in range(q): n, m, c_lib, c_road = map(int, input().split()) cities = [] for _ in range(m): cities.append(list(map(int, input().rstrip().split()))) result = roadsAndLibraries(n, c_lib, c_road, cities) print(result)