Submission #4541660


Source Code Expand

Copy
from scipy.sparse.csgraph import floyd_warshall
n,m = map(int,input().split())
d = [[float("inf")]*n for i in range(n)]
L = []
for i in range(n):
    d[i][i] = 0
for i in range(m):
    a,b,l = map(int,input().split())
    if a == 1:
        L.append([a,b,l])
    else:
        d[a-1][b-1] = l
        d[b-1][a-1] = l
d = floyd_warshall(d)
ans = float('inf')
for i in range(len(L)-1):
    for j in range(i+1,len(L)):
        ans = min(ans,L[i][2]+L[j][2]+d[L[i][1]-1][L[j][1]-1])
if ans == float('inf'):
  print(-1)
else:
  print(int(ans))

Submission Info

Submission Time
Task C - Blue Bird
User Syuko4omi
Language Python3 (3.4.3)
Score 100
Code Size 559 Byte
Status
Exec Time 477 ms
Memory 18036 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 100 / 100 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt
Case Name Status Exec Time Memory
sample_01.txt 256 ms 17632 KB
sample_02.txt 174 ms 13700 KB
sample_03.txt 172 ms 13700 KB
subtask1_01.txt 234 ms 15108 KB
subtask1_02.txt 214 ms 15236 KB
subtask1_03.txt 337 ms 16564 KB
subtask1_04.txt 176 ms 13700 KB
subtask1_05.txt 211 ms 14468 KB
subtask1_06.txt 347 ms 16516 KB
subtask1_07.txt 186 ms 14212 KB
subtask1_08.txt 179 ms 14212 KB
subtask1_09.txt 351 ms 16388 KB
subtask1_10.txt 249 ms 15124 KB
subtask1_11.txt 175 ms 13700 KB
subtask1_12.txt 207 ms 15492 KB
subtask1_13.txt 202 ms 14212 KB
subtask1_14.txt 175 ms 13956 KB
subtask1_15.txt 458 ms 17924 KB
subtask1_16.txt 292 ms 17028 KB
subtask1_17.txt 222 ms 16636 KB
subtask1_18.txt 329 ms 17276 KB
subtask1_19.txt 325 ms 17284 KB
subtask1_20.txt 245 ms 16772 KB
subtask1_21.txt 255 ms 16764 KB
subtask1_22.txt 422 ms 17756 KB
subtask1_23.txt 477 ms 18036 KB
subtask1_24.txt 248 ms 16772 KB
subtask1_25.txt 291 ms 17148 KB
subtask1_26.txt 383 ms 17668 KB
subtask1_27.txt 335 ms 17376 KB
subtask1_28.txt 226 ms 16644 KB
subtask1_29.txt 402 ms 17660 KB
subtask1_30.txt 198 ms 16516 KB