Roads in HackerLand
Roads in HackerLand
+ 2 comments why Floyd Warshall Algorithm is not working here?
+ 1 comment For those that are using Java to solve this problem, do not use BigInteger for calculating your total distance. Look for another solution.
+ 3 comments Edit - after discussing with @petrovovitch, I see that the shortcut I "discovered" is Kruskal's Minimum Spanning Tree algorithm, and has nothing to do with the edge weights being distinct or being powers of 2 - but either way, it does work. Subsequently counting edge use, as he suggests, is how I solved it as well.
+ 0 comments We have to calculate minimum distance between all the nodes. 1. First we built the MST using kruskal algo, and then 2. count the number of time each edge is used (using DFS traversal start from any vertex) 3. And then multiply the cost of the edge with it.
from collections import defaultdict n, m = map(int, input().split()) edges = [] parent = [i for i in range(n)] for _ in range(m): a, b, c = map(int, input().split()) edges.append((a-1, b-1, c)) def find(i): while i != parent[parent[i]]: parent[i] = parent[parent[i]] i = parent[i] return i def union(x, y): p_x = find(x) p_y = find(y) parent[p_y] = p_x def is_connected(x, y): p_x = find(x) p_y = find(y) return p_x == p_y # build MST tree = defaultdict(list) edges.sort(key = lambda x:x[2]) for a, b, c in edges: if not is_connected(a, b): union(a, b) tree[a].append((b, c)) tree[b].append((a, c)) ans = [0]*(2*m) # Run DFS to count the number of times an edge is used # as weights of all edges is different, hence each weight maps to a particular children def dfs(src, p = -1): total = 1 for v, c in tree[src]: if v != p: children = dfs(v, src) # children => nodes right to edge, n - children => nodes left to edge ans[c] += (n - children)*children total += children return total dfs(0) res = 0 for i in range(len(ans)): res += ans[i] * (1 << i) print(str(bin(res))[2:])
+ 2 comments With Python 3, I'm using Kruskal's algorithm to find the minimum spanning tree and then summing the edges as described by other posts here. This times out on test cases 11+, so I tried the Floyd-Warshall algorithm and that timed out even earlier. What can I do to optimize my solution enough to pass more cases?
Sort 36 Discussions, By:
Please Login in order to post a comment