提出 #4346206

ソースコード 拡げる

N=int(input())
inf=float("inf")
A=[list(map(int,input().split())) for _ in range(N)]

def calc():
    ans=0
    for i in range(N):
        for j in range(N):
            used=True
            for k in range(N):
                if i==k or k==j:continue
                if A[i][j]>A[i][k]+A[k][j]:
                    return -1
                elif A[i][j]==A[i][k]+A[k][j]:
                    used=False
            if used:
                ans+=A[i][j]
    return ans//2
                
print(calc())

提出情報

提出日時
問題 D - Restoring Road Network
ユーザ tallestorange
言語 Python (3.4.3)
得点 0
コード長 523 Byte
結果 TLE
実行時間 2104 ms
メモリ 6644 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 500
結果
AC × 4
AC × 9
TLE × 8
セット名 テストケース
Sample subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt
ケース名 結果 実行時間 メモリ
01.txt TLE 2104 ms 6644 KiB
02.txt TLE 2104 ms 6644 KiB
03.txt TLE 2104 ms 6644 KiB
04.txt TLE 2104 ms 6644 KiB
05.txt TLE 2104 ms 6644 KiB
06.txt TLE 2104 ms 6644 KiB
07.txt AC 112 ms 6644 KiB
08.txt TLE 2104 ms 6644 KiB
09.txt TLE 2104 ms 6644 KiB
10.txt AC 200 ms 6644 KiB
11.txt AC 68 ms 6644 KiB
12.txt AC 39 ms 6644 KiB
13.txt AC 18 ms 3064 KiB
subtask0_0.txt AC 17 ms 3064 KiB
subtask0_1.txt AC 17 ms 3064 KiB
subtask0_2.txt AC 18 ms 3064 KiB
subtask0_3.txt AC 17 ms 3060 KiB