This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define INF 1e18
using namespace std;
ll dp[50001][17][5][5],K,n,m,Q, ans[5][5], tmp[5][5];
void combine(ll target[5][5], ll a[5][5], ll b[5][5]) {
for (int i = 0; i < K; i++)
for (int j = 0; j < K; j++) {
target[i][j] = INF;
for (int mid = 0; mid < K; mid++)
target[i][j] = min(target[i][j],a[i][mid] + b[mid][j]);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> K >> n >> m >> Q;
int maxU = n/K + (n % K != 0);
for (int i = 0; i <= maxU; i++)
for (int j = 0; j <= 16; j++)
for (int k = 0; k < K; k++)
for (int l = 0; l < K; l++) dp[i][j][k][l] = INF;
for (int i = 1; i <= m; i++) {
int u,v,w;
cin >> u >> v >> w;
dp[u/K][0][u%K][v%K] = w;
}
for (int i = maxU; i >= 0; i--) {
for (int j = 1; i + (1 << j) - 1 <= maxU; j++) {
combine(dp[i][j],dp[i][j-1],dp[i + (1 << (j-1))][j-1]);
}
}
while (Q--) {
int u,v;
cin >> u >> v;
int U = u/K, V = v/K;
for (int i = 0; i < K; i++)
for (int j = 0; j < K; j++)
if (i != j) ans[i][j] = INF;
else ans[i][j] = 0;
for (int i = 16; i >= 0; i--) {
if (U + (1 << i) <= V) {
for (int i = 0; i < K; i++)
for (int j = 0; j < K; j++) tmp[i][j] = ans[i][j];
combine(ans,tmp,dp[U][i]);
U += (1 << i);
}
}
if (ans[u % K][v % K] == INF) cout << "-1\n";
else cout << ans[u % K][v % K] << '\n';
}
return 0;
}
/*
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |