Submission #1691804


Source Code Expand

def shortcutable(v, n, x, y):
    a = v[x][y]
    can_prunning = False
    for z in range(n):
        if not z in (x,y):
            b = v[x][z]
            c = v[z][y]
            #print(x,y,z,a,b,c)
            if (b + c) < a:
                return -1
            if (b + c) == a:
                can_prunning = True
    if can_prunning:
        #print(x,y,a)
        return 0
    else:
        return a

def solve(n, v):
    shortcuts = []
    total = 0
    for x in range(n):
        for y in range(x+1,n):
            result = shortcutable(v, n, x, y)
            if result < 0:
                return -1
            else:
                total += result
            #print(x,y,total)
    
    return total

n = int(input())
v = []
for i in range(n):
    v.append(list(map(int, input().split(" "))))

print(solve(v, n))

Submission Info

Submission Time
Task D - Restoring Road Network
User lanuvas
Language Python (3.4.3)
Score 0
Code Size 866 Byte
Status RE
Exec Time 43 ms
Memory 6772 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
RE × 4
RE × 17
Set Name Test Cases
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
Case Name Status Exec Time Memory
01.txt RE 43 ms 6772 KB
02.txt RE 40 ms 6644 KB
03.txt RE 40 ms 6644 KB
04.txt RE 39 ms 6644 KB
05.txt RE 39 ms 6644 KB
06.txt RE 40 ms 6644 KB
07.txt RE 39 ms 6644 KB
08.txt RE 39 ms 6644 KB
09.txt RE 38 ms 6644 KB
10.txt RE 40 ms 6644 KB
11.txt RE 39 ms 6644 KB
12.txt RE 39 ms 6644 KB
13.txt RE 18 ms 3064 KB
subtask0_0.txt RE 18 ms 3064 KB
subtask0_1.txt RE 18 ms 3064 KB
subtask0_2.txt RE 18 ms 3064 KB
subtask0_3.txt RE 18 ms 3064 KB