Submission #1127131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127131		sosuke	Toll (BOI17_toll)	Pypy 3	0 / 100	568 ms	180016 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], k)

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], k)
            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: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44