Tietoverkko

def GetInput():
    n = int(input())
    out=[(n,)]
    for i in range(n-1):
        a = input()
        out.append(tuple([int(b) for b in a.split()]))
    return out
exampleInput="""4
1 2 5
2 3 1
2 4 2
"""
exampleInput="""8
1 3 8
2 1 5
4 2 11
5 2 2
6 5 8
7 4 1
8 5 5
"""
exampleInput=[tuple([int(b) for b in a.split()]) for a in exampleInput.splitlines()]
I=exampleInput
I=GetInput()
n=I[0][0]
# yhteys voidaan kuvata virtaavan vain yhteen suuntaan? parin suuremmassa yksilössä on referenssi pienempään, 
# ja kun mennään koneiden listan läpi, mennään pienimmästä suurimpaan.
# voidaan huomata että ei ole mahdollista olla ympyröitä, joten jokaisesta koneesta on vain yksi reitti
koneet={}

for i in range(1,n):
    yhteys = I[i]
    b,a=yhteys[0:2]
    koneet.setdefault(yhteys[0],{})[yhteys[1]]=yhteys[2]
    koneet.setdefault(yhteys[1],{})[yhteys[0]]=yhteys[2]


def Crossroads(kone,source,sourceSpeed):
    # sourceSpeed = koneet[kone][source]
    haarat=[]
    addTotal=0
    for i in koneet[kone].keys()-{source}:
        speed=koneet[i][kone]
        c = Crossroads(i,kone,speed)
        haarat.append(c[0])
        addTotal+=c[1]

    yhteydet={sourceSpeed:1}
    for i in range(len(haarat)):
        yh=haarat[i]
        for j in yh.keys():
            if j<sourceSpeed:
                yhteydet.setdefault(j,0)
                yhteydet[j]+=yh[j]
            else:
                yhteydet[sourceSpeed]+=yh[j]
            addTotal+=haarat[i][j]*j
        for j in range(i):
            hi=haarat[i]
            for k in hi.keys():
                multiplier=hi[k]
                yht=haarat[j]
                for l in yht.keys():
                    addTotal+=yht[l]*min(l,k)*multiplier
    # yhteydet = {siirtonopeus:määrä}
    # addTotal = summaan lisättävä arvo joka tulee haaran välisistä yhteyksistä, + haarasta aiemmat addTotal
    return yhteydet,addTotal

an = Crossroads(1,0,0)


# print(I)
# print(koneet)
# print(an)

a=an[0]

total=an[1]
for i in a.keys():
    total+=a[i]*i
print(total)#-(10**9)

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED