save

import copy
path = []
path.append(left[0])
pathLen = 0
# print(list(G2.nodes))
leafs = []
leaf = {}
leaf['matrix'] = []
count = 0
maxInt = 1000000000


leaf['strMin'] = range(0,10)
leaf['colMin'] = range(0,10)
kk = []
for i in list(G2.nodes):
    leaf['matrix'].append([])
    for j in list(G2.nodes):
        leaf['matrix'][count].append(int(10000*G2[i][j]['weight']))
    leaf['matrix'][count][count] = maxInt
    count = count + 1

for i in leaf['matrix']:
    print(i)
S = 0

kk = copy.deepcopy(leaf['matrix'])
for i in range(0,len(list(G2.nodes))):
    minV = leaf['matrix'][0][i]
    for j in range(1,len(list(G2.nodes))):
        minV = min(minV,leaf['matrix'][j][i])
    for j in range(0,len(list(G2.nodes))):        
        leaf['matrix'][j][i] = leaf['matrix'][j][i] - minV
#     leaf['colMin'][i] = minV
    S = S + minV
for i in range(0,len(list(G2.nodes))):
    minV = leaf['matrix'][i][0]
    for j in range(1,len(list(G2.nodes))):
        minV = min(minV,leaf['matrix'][i][j])
    for j in range(0,len(list(G2.nodes))):        
        leaf['matrix'][i][j] = leaf['matrix'][i][j] - minV
#     leaf['strMin'][i] = minV
    S = S + minV   
    
# for i in range(0,len(list(G2.nodes))):
#     minV = leaf['matrix'][0][i]
#     for j in range(1,len(list(G2.nodes))):
#         if leaf['matrix'][j][i]>0:
#             minV = min(minV,leaf['matrix'][j][i])
#     leaf['colMin'][i] = minV
path2 = []
nn=[]
kk2 = copy.deepcopy(kk)
for k in range(0,10):
    print(nn)
    mm = maxInt
    xx = 0
    yy = 0
#     print(k)
#     for i in kk2:
#         print(i)
    for i in range(0,10):
        for j in range(0,10):
            if kk2[i][j]<mm:
                mm = kk2[i][j]
                xx = i
                yy = j
    if len(nn) == 0:
        nn.append([])
        nn[0].append(xx)
        nn[0].append(yy)
    else:
        ff = False
        xxx = []
        yyy = []
        for aa in nn:
            if xx in aa:
                ff = True
                xxx = aa
            if yy in aa:
                yyy = aa
                ff = True
        
        if len(xxx)>0 and len(yyy)>0:
            for pp in xxx:
                yyy.append(pp)
            nn.remove(xxx)
        else:    
            if ff:
                if len(xxx)>0:
                    xxx.append(yy)
                if len(yyy)>0:
                    yyy.append(xx)         
#             if xx in aa or yy in aa:
#                 ff = True
#                 if not(yy in aa):
#                     aa.append(yy)
#                 if not(xx in aa):
#                     aa.append(xx)
                
        if not(ff):
            nn.append([xx,yy])
#         if not(yy in nn):
#             nn.append(yy)
    path2.append([xx,yy])
    for aa in range(0,10):
        kk2[xx][aa] = maxInt
    for aa in range(0,10):
        kk2[aa][yy] = maxInt
    for aa in nn:
        for i in aa:
            for j in aa:
                kk2[i][j]=maxInt
print("path2") 
print(path2)
# for i in range(0,len(list(G2.nodes))):
#     minV = leaf['matrix'][i][0]
#     for j in range(1,len(list(G2.nodes))):
#         if leaf['matrix'][i][j]>0:
#             minV = min(minV,leaf['matrix'][i][j])
#     leaf['strMin'][i] = minV
    
leaf['S'] = S
leaf['d'] = 0
leaf['path'] = []
leaf['str'] = range(0,10)
leaf['col'] = range(0,10)
leaf['n'] = []
print(leaf)


import copy

leafs.append(leaf)
maxDepth = 10
found = False
minEnd = maxInt
path = []
last = S
while (not(found) or minEnd > last):
    num = 0
    count = 0
    node = leafs[0]
    for leaf in leafs:
        if node['S'] > leaf['S']:
            node = leaf
            num = count
        count = count + 1
#     print(num)
#     print("node d")
#     print(node['d'])
    last = node['S']
    if node['d'] == (maxDepth - 2):
        found = True
        path = node['path']
        path.append([node['str'][0], node['col'][0]])
        print(node['S'])
        minEnd = node['S']
    else:
        for i in node['matrix']:
            print(i)
#         leafL = node.copy()
        leafL = copy.deepcopy(node)
#         leafR = node.copy()
        leafR = copy.deepcopy(node)
#         print(leafR['S'] )
        maxFine = {}
        maxFine["num"] = -1
        maxFine["x"] = 0
        maxFine["y"] = 0
        
#         for i in range(0,maxDepth):
# #             minStr.append(maxInt)
#             for j in range(0,maxDepth):
        for i in node['str']:
#             minStr.append(maxInt)
            for j in node['col']:
                if (node['matrix'][i][j] == 0):
                    a = 0
                    ms = maxInt
                    mc = maxInt
                    for k in range(0,maxDepth):
                        if ms > node['matrix'][i][k] and not(k==j):
                            ms = node['matrix'][i][k]
                            
                    for k in range(0,maxDepth):
                        if mc > node['matrix'][k][j] and not(k==i):
                            mc = node['matrix'][k][j]
#                     print(ms+mc)
                    if (ms+mc > maxFine['num']):
                        maxFine['num'] = ms+mc
                        maxFine["x"] = i
                        maxFine["y"] = j
    
        print(maxFine['num'])
        print(maxFine['x'])
        print(maxFine['y'])
        leafL['matrix'][maxFine["x"]][maxFine["y"]] = maxInt
#         print(leafR['S'] )
        leafL['S'] = leafL['S'] + maxFine['num']
#         print(leafR['S'] )
        leafR['d'] += 1
        leafR['path'].append([maxFine["x"],maxFine["y"]])
        leafR['matrix'][maxFine["y"]][maxFine["x"]] = maxInt
        
        for k in range(0,maxDepth):
            leafR['matrix'][maxFine["x"]][k] = maxInt
            
#         print(leafR['str'])
#         print(maxFine["x"])
        leafR['str'].remove(maxFine["x"])
        
#         print(leafR['str'])
#         print(leafL['str'])
        
        for k in range(0,maxDepth):
            leafR['matrix'][k][maxFine["y"]] = maxInt
        
        leafR['col'].remove(maxFine["y"])
        
        if not(maxFine["y"] in leafR['n']):
            leafR['n'].append(maxFine["y"])
            
        if not(maxFine["x"] in leafR['n']):
            leafR['n'].append(maxFine["x"])
            
        for i in leafR['n']:
            for j in leafR['n']:
                leafR['matrix'][i][j]=maxInt
#         print(leafR['col'])
        
        S = 0
        for i in leafR['str']:
            minV = maxInt
            for j in leafR['col']:
                minV = min(minV,leafR['matrix'][i][j])
#             print(leafR['matrix'][i])
            for j in leafR['col']:        
                leafR['matrix'][i][j] = leafR['matrix'][i][j] - minV
#     leaf['strMin'][i] = minV
#             print(minV)
            S = S + minV

        for i in leafR['col']:
            minV = maxInt
            for j in leafR['str']:
                minV = min(minV,leafR['matrix'][j][i])
            for j in leafR['str']:        
                leafR['matrix'][j][i] = leafR['matrix'][j][i] - minV
#     leaf['strMin'][i] = minV
#             print(minV)
            S = S + minV
        print("S")
        print(S)
        leafR['S'] += S
        
        
        S = 0
        for i in leafL['str']:
            minV = maxInt
            for j in leafL['col']:
                minV = min(minV,leafL['matrix'][i][j])
#             print(leafR['matrix'][i])
            for j in leafL['col']:        
                leafL['matrix'][i][j] = leafL['matrix'][i][j] - minV
#     leaf['strMin'][i] = minV
#             print(minV)
            S = S + minV

        for i in leafL['col']:
            minV = maxInt
            for j in leafL['str']:
                minV = min(minV,leafL['matrix'][j][i])
            for j in leafL['str']:        
                leafL['matrix'][j][i] = leafL['matrix'][j][i] - minV
#     leaf['strMin'][i] = minV
#             print(minV)
            S = S + minV
        print("S")
        print(S)
        leafL['S'] += S
        
        
#         print(leafR['S'] )
        leafs.append(leafR)
        leafs.append(leafL)
        leafs.pop(num)
# #         leaf Left
#         for i in range(0,len(list(G2.nodes))):
        
    
print(path)


path.append([4,2])
Sum = 0
for i in path:
    Sum += kk[i[0]][i[1]]
print(Sum)