#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,tune=native")
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <fstream>
#include <algorithm>
#include <cstring> // Для memset
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;
const LL DIM = 50007;
const LL INF = 999999999999;
LL n, k, o, m;
class edge {
public:
LL to, w;
};
vector < edge > v[DIM];
class tran {
public:
int mat[5][5];
void init() {
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
mat[i][j] = INF;
}
}
}
};
tran* solve(LL L, LL R) {
tran* ans = new tran();
ans->init();
if (R - L == 1) {
for (int i = 0; i < k; i++) {
LL val = L * k + i;
for (auto to : v[val]) {
ans->mat[i][to.to - (R * k)] = to.w;
}
}
return ans;
}
LL mid = (L + R) / 2;
tran *m1 = solve(L, mid);
tran *m2 = solve(mid, R);
for (int l = 0; l < k; l++) {
for (int r = 0; r < k; r++) {
for (int m = 0; m < k; m++) {
ans->mat[l][r] = min(ans->mat[l][r], m1->mat[l][m] + m2->mat[m][r]);
}
}
}
delete m1;
delete m2;
return ans;
}
LL a, b, res, b1, b2;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> k >> n >> m >> o;
for (int i = 1; i <= m; i++) {
LL a, b, t;
cin >> a >> b >> t;
v[a].push_back({ b, t });
}
vector < LL > out;
for (int i = 1; i <= o; i++) {
cin >> a >> b;
b1 = a / k;
b2 = b / k;
if (b1 >= b2) out.push_back(-1);
else {
res = solve(b1, b2)->mat[a - b1 * k][b - b2 * k];
if (res >= INF) out.push_back(-1);
else out.push_back(res);
}
}
for (auto x : out) cout << x << endl;
return 0;
}
Compilation message (stderr)
toll.cpp: In member function 'void tran::init()':
toll.cpp:37:29: warning: overflow in conversion from 'LL' {aka 'long long int'} to 'int' changes value from '999999999999' to '-727379969' [-Woverflow]
37 | mat[i][j] = INF;
| ^~~
# | 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... |