#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = (int)1e9;
int K, N, M, Q;
vector<vector<vector<vector<int>>>> dp;
signed main() {
cin >> K >> N >> M >> Q;
dp.resize((N / K + 1) + 2, vector<vector<vector<int>>>(ceil(log2(N / K)) + 3,
vector<vector<int>>(K, vector<int>(K, INF))));
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 - 1)) <= (N + K - 1) / K; l++) {
for (int g = 0; g + (1 << l) < (N + K - 1) / K; 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, INF));
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)) + 2; l >= 0; l--) {
if ((len & (1 << l)) != 0) {
vector<vector<int>> tmp(K, vector<int>(K, INF));
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] == INF) {
cout << "-1\n";
} else {
cout << answer[a % K][b % K] << "\n";
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
197 ms |
83720 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
216 ms |
68292 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
26 ms |
1364 KB |
Output is correct |
8 |
Correct |
27 ms |
1272 KB |
Output is correct |
9 |
Correct |
191 ms |
83648 KB |
Output is correct |
10 |
Correct |
240 ms |
59708 KB |
Output is correct |
11 |
Correct |
222 ms |
68212 KB |
Output is correct |
12 |
Correct |
192 ms |
59628 KB |
Output is correct |
13 |
Correct |
185 ms |
37380 KB |
Output is correct |
14 |
Correct |
132 ms |
33876 KB |
Output is correct |
15 |
Correct |
124 ms |
37368 KB |
Output is correct |
16 |
Correct |
164 ms |
37364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Incorrect |
2 ms |
1376 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Incorrect |
2 ms |
1376 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
197 ms |
83720 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |