CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:Jellu
Submission time:2021-10-17 11:48:34
Language:CPython3
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1, 2, 3details
#2--2, 3details
#3--3details

Code

etaisyydet = {1:0}
yhteydet = {}
summa = 0
n = int(input())
for i in range(n-1):
    a,b,x = [int(x) for x in input().split()]
    etaisyydet[max(a,b)] = x
    if a not in yhteydet:
        yhteydet[a] = [b]
    else:
        yhteydet[a].append(b)
    if b not in yhteydet:
        yhteydet[b] = [a]
    else:
        yhteydet[b].append(a)
for i in range(1, n):
    c = 1
    a = i
    b = i + c
    pienin_arvo = 10**9 + 1
    while True:
        if a > b:
            pienin_arvo = min(pienin_arvo, etaisyydet[a])
            a = yhteydet[a][0]
        elif b > a:
            pienin_arvo = min(pienin_arvo, etaisyydet[b])
            b = yhteydet[b][0]
        elif a == b:
            c += 1
            a = i
            b = i + c
            summa += pienin_arvo
            pienin_arvo = 10**9 + 1
        if (i + c) == (n + 1):
            break
print(summa)

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
88687

Test 2

Group: 2, 3

Verdict:

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
(empty)

Test 3

Group: 3

Verdict:

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
(empty)