Submission #202475


Source Code Expand

#!/usr/bin/python                                                                                         
# -*- coding: utf-8 -*-                                                                                   
import sys
import math

REALSUM = 2025
N, M = map(int, sys.stdin.readline().rstrip().split())
INF = 10000

ansmap = [[INF for i in xrange(N)] for j in xrange(N)]

#buss = {}                                                                                                
for _ in xrange(M):
    a,b,t = map(int, sys.stdin.readline().rstrip().split())
    #buss[(a-1,b-1)] = t                                                                                  
    ansmap[a-1][b-1] = min(t, ansmap[a-1][b-1])
    ansmap[b-1][a-1] = min(t, ansmap[b-1][a-1])

# for i in xrange(N):                                                                                     
#     ansmap[i][i] = 0                                                                                    
#     for j in xrange(N):                                                                                 
#         if (i,j) in buss:                                                                               
#             ansmap[i][j] = buss[(i,j)]                                                                  
#         if (j,i) in buss:                                                                               
#             ansmap[i][j] = buss[(j,i)]                                                                  

for i in xrange(N):
    ansmap[i][i] = 0                                                                                      
    for j in xrange(N):
        ansmap[i][j] = min(ansmap[i][j], min([ansmap[i][k] + ansmap[k][j] for k in xrange(N)]))
        # for k in xrange(N):                                                                             
        #     ansmap[i][j] = min(ansmap[i][j], ansmap[i][k] + ansmap[k][j])                               

costs = [max(line) for line in ansmap]
print min(costs)


exit(0)

Submission Info

Submission Time
Task D - バスと避けられない運命
User hiking
Language Python (2.7.3)
Score 0
Code Size 2084 Byte
Status WA
Exec Time 5032 ms
Memory 4964 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 4
WA × 20
TLE × 12
Set Name Test Cases
All test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt
Case Name Status Exec Time Memory
sample_01.txt AC 49 ms 3492 KB
sample_02.txt AC 49 ms 3496 KB
sample_03.txt AC 48 ms 3508 KB
test_01.txt AC 48 ms 3500 KB
test_02.txt TLE 5030 ms 4268 KB
test_03.txt TLE 5031 ms 4964 KB
test_04.txt AC 3369 ms 4644 KB
test_05.txt WA 3090 ms 3964 KB
test_06.txt WA 308 ms 3500 KB
test_07.txt TLE 5031 ms 4664 KB
test_08.txt WA 60 ms 3500 KB
test_09.txt WA 2091 ms 3884 KB
test_10.txt WA 266 ms 3440 KB
test_11.txt WA 310 ms 3448 KB
test_12.txt TLE 5030 ms 4088 KB
test_13.txt WA 321 ms 3500 KB
test_14.txt WA 477 ms 3636 KB
test_15.txt TLE 5030 ms 4544 KB
test_16.txt WA 544 ms 3556 KB
test_17.txt WA 2432 ms 4012 KB
test_18.txt WA 4589 ms 4012 KB
test_19.txt WA 598 ms 3624 KB
test_20.txt AC 495 ms 3452 KB
test_21.txt AC 50 ms 3504 KB
test_22.txt WA 1566 ms 3760 KB
test_23.txt WA 55 ms 3496 KB
test_24.txt TLE 5031 ms 4160 KB
test_25.txt TLE 5030 ms 4220 KB
test_26.txt WA 2051 ms 3676 KB
test_27.txt WA 2774 ms 3764 KB
test_28.txt TLE 5030 ms 4264 KB
test_29.txt TLE 5030 ms 4196 KB
test_30.txt WA 433 ms 3504 KB
test_31.txt WA 73 ms 3504 KB
test_32.txt TLE 5030 ms 4216 KB
test_33.txt TLE 5031 ms 4148 KB
test_34.txt WA 175 ms 3496 KB
test_35.txt WA 1666 ms 3644 KB
test_36.txt TLE 5032 ms 4144 KB