FWATER - Tưới nước đồng cỏ

Tác giả: khuc_tuan

Ngôn ngữ: Python

import gc  
gc.disable()  
import sys
import psyco
psyco.full() 

def main():

    n = input()
    C = [[0 for i in range(n+1)] for j in range(n+1)]
    
    for i in range(n):
        C[i+1][0] = C[0][i+1] = input()
        
    for i in range(1,n+1):
        T = [int(s) for s in raw_input().split()]
        for j in range(1,n+1):
            C[i][j] = T[j-1]
            
    inT = [False for i in range(n+1)]
    inT[0] = True
    nearest = [i for i in C[0]]
    
    total = 0
    
    for kk in range(n):
        min = 1000000000
        imin = -1
        for i in range(1,n+1):
            if (not inT[i]) and (nearest[i]<min):
                min = nearest[i]
                imin = i
            
        total += min
                
        assert not imin==-1
        
        inT[imin] = True
        for i in range(1,n+1):
            if (not inT[i]) and (C[i][imin]<nearest[i]):
                nearest[i] = C[i][imin]
                
    print total
    
    
main()

Download