Submission #1127133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127133		sosuke	Toll (BOI17_toll)	Pypy 3	100 / 100	1208 ms	202912 KiB

toll

MAX_K = 5
MAX_J = 17
INF = float('inf')

def combine(target: list[list[int]], a: list[list[int]], b: list[list[int]]):
    for x in range(k):
        for y in range(k):
            for z in range(k):
                target[x][y] = min(target[x][y], a[x][z] + b[z][y])


k, n, m, o = map(int, input().split())

dp = [[[[INF] * k for _ in range(k)] for _ in range(MAX_J)] for _ in range((n + k - 1) // k)]

for _ in range(m):
    a, b, t = map(int, input().split())
    dp[a // k][0][a % k][b % k] = t

for j in range(1, MAX_J):
    for i in range((n + k - 1) // k - (1 << j)):
        combine(dp[i][j], dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1])

for _ in range(o):
    a, b = map(int, input().split())
    
    ans = [[INF] * k for _ in range(k)]
    for i in range(k):
        ans[i][i] = 0
    
    curr = a // k
    dest = b // k
    
    for i in range(MAX_J - 1, -1, -1):
        if curr + (1 << i) <= dest:
            tmp = [[INF] * k for _ in range(k)]
            combine(tmp, ans, dp[curr][i])
            ans = tmp
            curr += (1 << i)
    
    print(-1 if ans[a % k][b % k] == INF else ans[a % k][b % k])

Compilation message (stdout)

Compiling 'toll.py'...

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

=======

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44