#include <bits/stdc++.h>
using namespace std;
int K, N, M, Q;
vector<vector<vector<vector<int>>>> dp;
int main() {
cin >> K >> N >> M >> Q;
dp.resize((N / K + 1), vector<vector<vector<int>>>(ceil(log2(N / K)) + 1,
vector<vector<int>>(K, vector<int>(K, INT_MAX / K))));
for (int i = 0; i < M; i++) {
int a, b, c; cin >> a >> b >> c;
dp[a / K][0][a % K][b % K] = c;
}
for (int l = 1; (1 << l) <= (N + K - 1) / K; l++) {
for (int g = 0; g < (N + K - 1) / K - (1 << l); g++) {
for (int x = 0; x < K; x++) {
for (int y = 0; y < K; y++) {
for (int z = 0; z < K; z++) {
dp[g][l][x][y] = min(dp[g][l][x][y],
dp[g][l - 1][x][z] + dp[g + (1 << (l - 1))][l - 1][z][y]);
}
}
}
}
}
for (int i = 0; i < Q; i++) {
int a, b; cin >> a >> b;
vector<vector<int>> answer(K, vector<int>(K, INT_MAX / K));
for (int j = 0; j < K; j++) {
answer[j][j] = 0;
}
int len = b / K - a / K, lst = a / K;
for (int l = ceil(log2(len)) + 1; l >= 0; l--) {
if ((len & (1 << l)) != 0) {
vector<vector<int>> tmp(K, vector<int>(K, INT_MAX / K));
for (int x = 0; x < K; x++) {
for (int y = 0; y < K; y++) {
for (int z = 0; z < K; z++) {
tmp[x][y] = min(tmp[x][y], answer[x][z] + dp[lst][l][z][y]);
}
}
}
answer = tmp;
lst |= (1 << l);
}
}
if (answer[a % K][b % K] >= INT_MAX / K) {
cout << "-1\n";
} else {
cout << answer[a % K][b % K] << "\n";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
197 ms |
75052 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
216 ms |
60936 KB |
Output is correct |
2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
197 ms |
75052 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |