Skip to content

Instantly share code, notes, and snippets.

@NeatMonster
Last active December 18, 2015 16:59
Show Gist options
  • Save NeatMonster/5815272 to your computer and use it in GitHub Desktop.
Save NeatMonster/5815272 to your computer and use it in GitHub Desktop.
# -*- coding: cp1252 -*-
if __name__ == '__main__':
raw_input()
n = int(raw_input())
roads = [[int(_) for _ in raw_input().split()] for i in xrange(n)]
roads = sorted(roads, cmp=lambda x, y: cmp(x[2], y[2]))
sets, kms = [], 0
for road in roads:
added = False
for set in sets:
if (road[0] in set and road[1] not in set) or (road[0] not in set and road[1] in set):
added = True
kms += road[2]
set.add(road[0])
set.add(road[1])
for other_set in sets:
if other_set != set and (road[0] in other_set or road[1] in other_set):
set.update(other_set)
other_set.clear()
break
break
elif road[0] in set and road[1] in set:
added = True
break
if not added:
kms += road[2]
sets.append({road[0], road[1]})
print kms
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment