Problem:
Problem F: Computation of Minimum Length of Pipeline The Aizu Wakamatsu city office decided to lay a hot water pipeline covering the whole area of the city to heat houses. The pipeline starts from some hot springs and connects every district in the city. The pipeline can fork at a hot spring or a district, but no cycle is allowed. The city office wants to minimize the length of pipeline in order to build it at the least possible expense. Write a program to compute the minimal length of the pipeline. The program reads an input that consists of the following three parts: Input  The first part consists of two positive integers in one line, which represent the number s of hot springs and the number d of districts in the city, respectively.  The second part consists of s lines: each line contains d non-negative integers. The i -th integer in the j -th line represents the distance between the j -th hot spring and the i -th district if it is non-zero. If zero it means they are not connectable due to an obstacle between them.  The third part consists of d -1 lines. The i -th line has d - i non-negative integers. The i -th integer in the j -th line represents the distance between the j -th and the ( i + j )-th districts if it is non-zero. The meaning of zero is the same as mentioned above.  For the sake of simplicity, you can assume the following:  The number of hot springs and that of districts do not exceed 50.  Each distance is no more than 100.  Each line in the input file contains at most 256 characters.  Each number is delimited by either whitespace or tab.  The input has several test cases. The input terminate with a line which has two 0. The number of test cases is less than 20. Output Output the minimum length of pipeline for each test case. Sample Input 3 5
12 8 25 19 23
9 13 16 0 17
20 14 16 10 22
17 27 18 16
9 7 0
19 5
21
0 0 Output for the Sample Input 38 Hint The first line correspondings to the first part: there are three hot springs and five districts. The following three lines are the second part: the distances between a hot spring and a district. For instance, the distance between the first hot spring and the third district is 25. The last four lines are the third part: the distances between two districts. For instance, the distance between the second and the third districts is 9. The second hot spring and the fourth district are not connectable The second and the fifth districts are not connectable, either.

Solution (Python):



import sys
from sys import stdin
input = stdin.readline
import heapq

while True:
	s, d = map(int, input().split())
	if s == 0: break
	visited = [0]*100
	Q = []
	to = [[] for i in range(100)]
	for i in range(s):
		visited[i] = 1
		c = list(map(int, input().split()))
		for j in range(d):
			if c[j] > 0: heapq.heappush(Q, (c[j], i, s+j))
	for i in range(d-1):
		c = list(map(int, input().split()))
		for j in range(i+1, d):
			if c[j-i-1] > 0:
				to[s+i].append((s+j, c[j-i-1]))
				to[s+j].append((s+i, c[j-i-1]))

	ans = k = 0
	while k < d:
		while True:
			c, a, b = heapq.heappop(Q)
			if visited[a] == 0 or visited[b] == 0: break
		ans, k = ans+c, k+1
		if visited[a]: a = b
		visited[a] = 1;
		for e, c in to[a]:
			if visited[e] == 0:	heapq.heappush(Q, (c, a, e))
	print(ans)

Solution (Python):
class UnionFind:
  def __init__(self, size):
    self.table = [-1 for _ in xrange(size)]

  def find(self, x):
    while self.table[x] >= 0: x = self.table[x]
    return x

  def union(self, x, y):
    s1 = self.find(x)
    s2 = self.find(y)
    if s1 != s2:
      if self.table[s1] >= self.table[s2]:
        self.table[s1] += self.table[s2]
        self.table[s2] = s1
      else:
        self.table[s2] += self.table[s1]
        self.table[s1] = s2
      return True
    return False

def hash(n, s, g):
  return n*s+g

def dehash(n, hs):
  return [(hs-hs%n)/n, hs%n]

def kruskal(n, path):
  path = sorted(path.items(), key=lambda x:x[1])
  selected = {}
  union = UnionFind(n)
  for i in xrange(len(path)):
    k,v = path[i]
    s,g = dehash(n, k)
    if union.union(s, g):
      selected[k] = v
  return selected


while True:
  s,d = map(int, raw_input().split())
  if s==d==0:
    break
  path = {}
  n = 1 + d
  
  for i in xrange(s):
    ipt = raw_input().split()
    for j in xrange(d):
      if ipt[j] != "0":
        if hash(n, 0, 1+j) in path:
          path[hash(n, 0, 1+j)] = min(path[hash(n, 0, 1+j)], int(ipt[j]))
        else:
          path[hash(n, 0, 1+j)] = int(ipt[j])

  
  for i in xrange(d-1):
    ipt = raw_input().split()
    for j in xrange(d-i-1):
      if ipt[j] != "0":
        path[hash(n, 1+i, i+j+2)] = int(ipt[j])

  result = kruskal(n, path)
  sumcost = 0
  for v in result.values():
    sumcost += v
  print sumcost

Solution (Python):
while(1):
    s,d=[int(x) for x in input().split()]
    A=[999 for x in range(d)]
    if s==0:    break
    for j in range(s):
        l=[int(x) for x in input().split()]
        for i in range(d):
            if l[i]!=0:
                A[i]=min(A[i], l[i]) 
    B=[[999 for x in range(d)] for y in range(d)]
    for j in range(d-1):
        l=[int(x) for x in input().split()]
        for i in range(d-1-j):
            if l[i]!=0:
                B[j][i+j+1]=l[i]
                B[i+j+1][j]=l[i]
    notevaled=[1 for x in range(d)]
    ans=0
    for i in range(d):
        mini=A.index(min(A))
        ans+=A[mini]
        notevaled[mini]=0
        A[mini]=999
        for x in range(d):
            if notevaled[x]:
                A[x]=min( A[x], B[mini][x] )
    print(ans)