Submission #1171890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171890		Isam	Autobus (COCI22_autobus)	Pypy 3	30 / 70	1035 ms	56524 KiB

Main

INF = int(1e9 + 7)

def solve():
    n, m = map(int, input().split())
    
    dp = [[[INF for _ in range(75)] for _ in range(75)] for _ in range(75)]
    
    for i in range(1, 72):
        for j in range(i, 72):
            for l in range(75):
                dp[i][j][l] = dp[j][i][l] = INF
    
    for i in range(1, n+1):
        dp[i][i][0] = 0
    
    for _ in range(m):
        a, b, t = map(int, input().split())
        dp[a][b][1] = min(dp[a][b][1], t)
    
    K, Q = map(int, input().split())
    
    for k in range(1, min(K + 1, 71)):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                for l in range(1, n + 1):
                    if dp[i][l][k - 1] != INF and dp[l][j][1] != INF:
                        dp[i][j][k] = min(dp[i][j][k], dp[i][l][k - 1] + dp[l][j][1])

    for _ in range(Q):
        u, v = map(int, input().split())
        ans = INF
        for i in range(min(K + 1, 71)):
            ans = min(ans, dp[u][v][i])
        print(-1 if ans == INF else ans)

solve()

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 52%)

=======

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15