#include "bits/stdc++.h"
using namespace std;
#include "Deb.h"
const int Log = 17;
const long long INF = 1e15;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k, n, m, q;
cin >> k >> n >> m >> q;
vector<vector<vector<long long>>> jump(Log, vector<vector<long long>> (n, vector<long long> (k, INF)));
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
jump[0][u][v % k] = w;
}
map<int, int> mp;
for (int i = 0; i < Log; ++i) {
mp[1 << i] = i;
}
for (int bit = 1; bit < Log; ++bit) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < k; ++j) {
int x = i - (i % k) + (1 << (bit - 1)) * k + j;
if (x >= n) {
break;
}
for (int l = 0; l < k; ++l) {
jump[bit][i][l] = min(jump[bit][i][l], jump[bit - 1][i][j] + jump[bit - 1][x][l]);
}
}
}
}
while (q--) {
int u, v;
cin >> u >> v;
int diff = v / k - u / k;
if (diff <= 0) {
cout << -1 << '\n';
continue;
}
vector<pair<int, long long>> vec = {{u, 0}};
while (diff) {
int lsb = diff & -diff;
int ind = mp[lsb];
diff -= lsb;
vector<pair<int, long long>> nvec;
int org = vec.back().first;
org -= org % k;
for (int i = 0; i < k; ++i) {
int nnode = org + lsb * k + i;
if (nnode >= n) {
break;
}
nvec.push_back({org + lsb * k + i, INF});
}
for (auto [x, y] : vec) {
for (int j = 0; j < k; ++j) {
nvec[j].second = min(nvec[j].second, y + jump[ind][x][j]);
}
}
vec = nvec;
}
bool f = false;
for (auto [i, j] : vec) {
if (i == v && j < INF) {
cout << j << '\n';
f = true;
break;
}
}
if (!f) {
cout << -1 << '\n';
}
}
return 0;
}
Compilation message
toll.cpp:4:10: fatal error: Deb.h: No such file or directory
4 | #include "Deb.h"
| ^~~~~~~
compilation terminated.
