CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:tassu
Submission time:2021-10-05 16:39:27
Language:CPython3
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.02 s1, 2, 3details
#20.03 s2, 3details
#30.02 s3details

Code

import math

import numpy as np

costs = np.matrix([
    [0, 5, 0, 0],
    [5, 0, 1, 2],
    [0, 1, 0, 0],
    [0, 2, 0, 0],
])


l = len(costs)


def find_lowest(unvisited, distances):
    smallest_key, smallest_value = 0, math.inf
    for key in unvisited:
        value = distances[key]
        if value < smallest_value:
            smallest_key = key
    return smallest_key


def speeds_for(initial):
    unvisited = list(range(l))
    distance = [0 if i == initial else math.inf for i in unvisited]
    speeds = [math.inf for _ in unvisited]
    unvisited.remove(initial)

    current = initial

    speed_counter = 0

    while True:
        current_distance = distance[current]
        current_speed = speeds[current]

        for j in unvisited:
            speed = costs[j, current]
            if speed == 0:
                continue

            distance[j] = current_distance + 1
            min_speed = min(current_speed, speed)
            speeds[j] = min_speed
            speed_counter += min_speed

        if len(unvisited) == 0:
            break

        current = find_lowest(unvisited, distance)
        unvisited.remove(current)

    return speed_counter


total_speed = 0
for i in range(l):
    total_speed += speeds_for(i)

print(int(total_speed / 2))

Test details

Test 1

Group: 1, 2, 3

Verdict:

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

correct output
88687

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 3, in <module>
    import numpy as np
ModuleNotFoundError: No module named 'numpy'

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 3, in <module>
    import numpy as np
ModuleNotFoundError: No module named 'numpy'

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 3, in <module>
    import numpy as np
ModuleNotFoundError: No module named 'numpy'