Sadonkorjuu

#import math
#import numpy
import math
#import datetime	
CityCount = int(input())
CityStates = input().split()
RoadList = []
#Build a nested array of roads
for n in range(0,CityCount-1):
    temp = input().split()
    RoadList.append(temp)
#start_time = datetime.datetime.now()
 
#Convert to numpy array
#RoadMatrix = numpy.array(RoadList)
 
RoadDict = {}
Ports = []
#Cycle through roads to find ones that connect to a given node, then build a dictionary which indexes each connected road
for a in range(0,CityCount):
    tempList = []
    #Roads
    for b in range(0, CityCount-1):
        if(int(RoadList[b][0]) == a+1):
           tempList.append([int(RoadList[b][1])-1,int(RoadList[b][2])])
        elif(int(RoadList[b][1]) == a+1):
           tempList.append([int(RoadList[b][0])-1,int(RoadList[b][2])])
    if not int(CityStates[a]):
        Ports.append(a)
    #Cycle them through again, rearraging them in ascending weight
    for b in range(0, len(tempList)):
        tempList.sort(key= lambda x: x[1])
    RoadDict[a] = tempList
#Actually find something
currentNode = 0
nodeDistances = [0]+[math.inf]*(CityCount-1)
totalDistances = 0
 
unvisited_nodes = [x for x in range(CityCount)]
#shortest_path = {}
#previous_nodes = {}
#start_node = 0
 
def connection(node, target):
    node = node
    target = target
    for con in RoadDict[node]:
        if(int(con[0]) == target):
            return int(con[1])
    return 0
 
def Neighbors(node):
    return RoadDict[node]            
 
def Distance(nodeList):
    totalDistance = 0
    for nodeIndex in range(0,len(nodeList)-1):
        totalDistance += connection(nodeList[nodeIndex], nodeList[nodeIndex+1])
    return totalDistance
 
class Tree():
    def __init__(self, parent, history):
        self.parent = parent
        self.children = []
        self.history = history
    def addChild(self, child):
        self.children.append(child)
 
class Node():
    def __init__(self, nodeVal) -> None:
        self.value = nodeVal
        self.root = None
        self.distance = math.inf
    def setParent(self, root):
        self.root = root
    def addDistance(self, distance):
        if(distance < self.distance):
            self.distance = distance
    def __repr__(self) -> str:
        return 
 
#Initialize nodes:
NodeList = []
for i in range(0, CityCount):
    NodeList.append(Node(i))
    if not int(CityStates[i]):
        NodeList[i].addDistance(0)

PortNodes = []
for i in range(0, len(Ports)):
    PortNodes.append(NodeList[Ports[i]])
bingus=[]
EndNode = [[] for _ in range(CityCount)]
sum = 0
for startingNode in PortNodes:
    #treeList = []
    node = startingNode
    startingNodevalue = startingNode.value
    travelledNodes = [False]*CityCount
    #nodeIterator = 0
    Queue = []
    Queue.append(startingNode)
    NodeStates = {}
    travelledNodes[startingNodevalue] = True
    #if CityStates[startingNodevalue] == "0":
    #    EndNode[startingNodevalue].append(startingNode)
    #else:
    while Queue:
        node = Queue[0]
        #root = Tree(node, None)
        Queue.pop(0)
        smallestWeight = math.inf
        smallestWeightNode = 0
        portNotFound = True
        nodeValue = node.value 
        for neighbor in RoadDict[nodeValue]:
            neighborNode = NodeList[neighbor[0]]
            if(CityStates[neighbor[0]] == "0"):
                travelledNodes[neighbor[0]] = True

            elif(not travelledNodes[neighbor[0]]):
                #    neighborNode.setParent(node)
                travelledNodes[neighbor[0]] = True
                Queue.append(neighborNode)
                neighborNode.setParent(node)
                neighborNode.addDistance(connection(nodeValue, neighborNode.value)+node.distance)
        #        if(CityStates[neighbor[0]] == "0"):
         #           EndNode[startingNode.value].append(neighborNode) 
    DistanceIterator = 0
    smallestDistance = math.inf
    #for leaf in EndNode[startingNodevalue]:
    #    cahceNode = leaf
    #    wtfdistance = 0
    #    lastNode = cahceNode.value
    #    Distances = []
    #    distance = 0
    #    while True:
    #        if cahceNode.value == startingNodevalue:
    #            #distance += connection(cahceNode.value, lastNode)
    #            for con in RoadDict[cahceNode.value]:
    #                if con[0] == lastNode:
    #                    distance += con[1]
    #                    break
    #            break
    #            #print(distance, " , for node ", startingNode.value)
    #        else:
    #            for con in RoadDict[cahceNode.value]:
    #                if con[0] == lastNode:
    #                    distance += con[1]
    #                    break
    #            lastNode = cahceNode.value
    #            cahceNode = cahceNode.root
    #    if smallestDistance > distance:
    #        smallestDistance = distance
    #    #DistanceIterator +=1
 
    #sum += smallestDistance
#    print(smallestDistance)
for node in NodeList:
    sum += node.distance
print(sum)
#end_time = datetime.datetime.now()
#print(end_time - start_time)

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 1, 2

Verdict: ACCEPTED

Test 16

Group: 1, 2

Verdict: ACCEPTED

Test 17

Group: 1, 2

Verdict: ACCEPTED

Test 18

Group: 1, 2

Verdict: ACCEPTED

Test 19

Group: 1, 2

Verdict: ACCEPTED

Test 20

Group: 1, 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 1, 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 1, 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: TIME LIMIT EXCEEDED