CSES - Datatähti 2023 alku - Results
Submission details
Task:Ruudukko
Sender:Finnduino
Submission time:2022-11-06 03:01:45 +0200
Language:PyPy3
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.04 s1, 2, 3details
#20.04 s1, 2, 3details
#30.07 s1, 2, 3details
#40.06 s2, 3details
#50.05 s2, 3details
#60.07 s2, 3details
#70.52 s3details
#80.32 s3details
#90.34 s3details

Code

#import math
#import numpy
import math

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)

#Convert to numpy array
#RoadMatrix = numpy.array(RoadList)

RoadDict = {}

#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])])
    
    #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
    def setParent(self, root):
        self.root = root
    def __repr__(self) -> str:
        return 

#Initialize nodes:
NodeList = []
for i in range(0, CityCount):
    NodeList.append(Node(i))

bingus=[]
EndNode = [[]]*CityCount
sum = 0
for startingNode in NodeList:
    #treeList = []
    node = startingNode
    travelledNodes = [False]*CityCount
    #nodeIterator = 0
    Queue = []
    Queue.append(startingNode)
    NodeStates = {}
    travelledNodes[startingNode.value] = True
    while Queue:
        node = Queue[0]
        #root = Tree(node, None)
        Queue.pop(0)
        smallestWeight = math.inf
        smallestWeightNode = 0
        portNotFound = True
        #newSmallest = False
        
        #if CityStates[node.value] == "0":
                #Found a port
                
                #print(EndNode)
         #       portNotFound = False

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

    sum += smallestDistance
    print(smallestDistance)
print(sum)


                

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
3
1 1 1
1 1 1
1 1 1

correct output
9

user output
inf
inf
inf
inf

Test 2

Group: 1, 2, 3

Verdict:

input
3
1 2 3
6 5 4
7 8 9

correct output
135

user output
inf
inf
inf
inf

Test 3

Group: 1, 2, 3

Verdict:

input
3
7 8 1
4 5 4
3 9 6

correct output
57

user output
inf
inf

Error:
Traceback (most recent call last):
  File "input/code.py", line 111, in <module>
    neigh...

Test 4

Group: 2, 3

Verdict:

input
100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
10000

user output
inf
inf
inf
inf
inf
...
Truncated

Test 5

Group: 2, 3

Verdict:

input
100
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
187458477

user output
inf
inf
inf
inf
inf
...
Truncated

Test 6

Group: 2, 3

Verdict:

input
100
2995 8734 1018 2513 7971 5063 ...

correct output
964692694

user output
inf
inf
inf
inf
inf
...

Error:
Traceback (most recent call last):
  File "input/code.py", line 111, in <module>
    neigh...

Test 7

Group: 3

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1000000

user output
inf
inf
inf
inf
inf
...
Truncated

Test 8

Group: 3

Verdict:

input
1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
229147081

user output
inf
inf
inf
inf
inf
...
Truncated

Test 9

Group: 3

Verdict:

input
1000
520283 805991 492643 75254 527...

correct output
951147313

user output
inf
inf
inf
inf
inf
...
Truncated

Error:
Traceback (most recent call last):
  File "input/code.py", line 111, in <module>
    neigh...