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.



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


Sample output:
38

Submission status: Wrong Answer

Solution code:
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

# main
while True:
  s,d = map(int, raw_input().split())
  if s==d==0:
    break
  path = {}
  n = s + d
  # springs are connected
  for i in xrange(s):
    path[hash(n, i, i+1)] = 0
  # distance between springs and districts
  for i in xrange(s):
    ipt = raw_input().split()
    for j in xrange(d):
      if ipt[j] != "0":
        path[hash(n, i, s+j)] = int(ipt[j])
  # distance betweend districts
  for i in xrange(d-1):
    ipt = raw_input().split()
    for j in xrange(d-i-1):
      if ipt[j] != "0":
        path[hash(n, s+i, s+i+j+1)] = int(ipt[j])

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

Submission status: Wrong Answer

Solution code:
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[i][i+j+1]=l[i]
                B[i+j+1][i]=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)

Submission status: Accepted

Solution code:
# AOJ 1014: Computation of Minimum Length of Pipeline
# Python3 2018.7.5 bal4u

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)

Submission status: Accepted

Solution code:
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

# main
while True:
  s,d = map(int, raw_input().split())
  if s==d==0:
    break
  path = {}
  n = 1 + d
  # distance between springs and districts
  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])

  # distance betweend districts
  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

Submission status: Accepted

Solution code:
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)