#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
vector<vector<int>> combine(vector<vector<int>> &a, vector<vector<int>> &b){
int k = a.size();
vector<vector<int>> res(k, vector<int>(k, INF));
for (int i = 0; i < k; i++){
for (int j = 0; j < k; j++){
for (int z = 0; z < k; z++){
res[i][j] = min(res[i][j], a[i][z] + b[z][j]);
}
}
}
return res;
}
void Solve()
{
int k, n, m, q; cin >> k >> n >> m >> q;
vector<vector<vector<vector<int>>>> dp((n/k) + 1, vector<vector<vector<int>>>(18, vector<vector<int>>(k, vector<int>(k, INF))));
for (int i = 1; i <= m; i++){
int a, b, t; cin >> a >> b >> t;
dp[a/k][0][a % k][b % k] = t;
}
for (int j = 1; j < 18; j++){
for (int i = 0; i <= n/k; i++){
//combine dp[i][j - 1] and dp[i + (1 << (j - 1))][j - 1]
int x = i + (1 << (j - 1));
if (x <= (n/k))
dp[i][j] = combine(dp[i][j - 1], dp[x][j - 1]);
}
}
while (q--){
int a, b; cin >> a >> b;
int x = a / k;
int y = b / k;
int diff = y - x;
//lift diff times
vector<vector<int>> res(5, vector<int>(5, INF));
res[a % k][a % k] = 0;
for (int i = 17; i >= 0; i--){
if (diff >> i & 1){
res = combine(res, dp[x][i]);
x += 1 << i;
}
}
int ans = INF;
for (int i = 0; i < k; i++){
ans = min(ans, res[i][b % k]);
}
if (ans == INF) ans = -1;
cout << ans << "\n";
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
202 ms |
162380 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
182 ms |
139716 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
448 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
448 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
202 ms |
162380 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |