#include<bits/stdc++.h>
#include<math.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N = 5e4 + 5, oo = 1e18;
int t, dist[N][5][5], d[N][5][5], n, k, m, q, ans[N];
vector<int> cur[N];
pair<int, int> p[N];
void solve(int l, int r, vector<int> v) {
if (l == r) return;
int mid = (l + r) / 2;
vector<int> x, y;
for (int i = l; i <= r; i++) cur[i].clear();
for (int i = 0; i < v.size(); i++) {
int ind = v[i];
if (p[ind].s / k <= mid) x.push_back(v[i]);
else if (p[ind].f / k >= mid + 1) y.push_back(v[i]);
else cur[p[ind].s / k].push_back(v[i]);
}
for (int j = 0; j < k; j++) {
for (int x = 0; x < k; x++) {
d[mid + 1][j][x] = 0;
}
}
for (int i = mid; i >= l; i--) {
for (int from = 0; from < k; from++) {
for (int to = 0; to < k; to++) {
d[i][from][to] = oo;
for (int j = 0; j < k; j++) {
if(i == mid) d[i][from][to] = dist[i][from][to];
else d[i][from][to] = min(d[i][from][to], d[i + 1][j][to] + dist[i][from][j]);
}
}
}
}
for (int i = mid + 2; i <= r; i++) {
for (int from = 0; from < k; from++) {
for (int to = 0; to < k; to++) {
d[i][from][to] = oo;
for (int j = 0; j < k; j++) {
if(i == mid+2) d[i][from][to] = dist[i-1][to][from];
else d[i][from][to] = min(d[i][from][to], d[i - 1][j][to] + dist[i-1][j][from]);
}
}
}
}
for (int i = mid + 1; i <= r; i++) {
for (int j = 0; j < cur[i].size(); j++) {
int ind = cur[i][j];
ans[ind] = oo;
for (int x = 0; x < 5; x++) {
for (int y = 0; y < 5; y++)
ans[ind] = min(ans[ind], d[p[ind].f / k][p[ind].f % k][x]
+ d[i][p[i].s % k][y] + dist[mid][x][y]);
}
if (i == mid + 1) ans[ind] = d[p[ind].f / k][p[ind].f % k][p[ind].s % k];
}
}
solve(l, mid, x);
solve(mid + 1, r, y);
}
signed main() {
cin >> k >> n >> m >> q;
for (int i = 0; i <= n / k; i++) {
for (int j = 0; j < k; j++) {
for (int x = 0; x < k; x++) dist[i][j][x] = oo;
}
}
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
dist[u / k][u % k][v % k] = w;
}
vector<int> all;
for (int i = 1; i <= q; i++) {
cin >> p[i].f >> p[i].s;
ans[i] = oo;
if (p[i].s <= p[i].f) ans[i] = -1;
else all.push_back(i);
}
solve(0, n / k, all);
for (int i = 1; i <= q; i++) {
if (ans[i] == oo) cout << -1;
else cout << ans[i];
cout << "\n";
}
}
Compilation message
toll.cpp: In function 'void solve(long long int, long long int, std::vector<long long int>)':
toll.cpp:16:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
toll.cpp:53:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int j = 0; j < cur[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
104 ms |
21828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
130 ms |
11996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
1484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
1484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
104 ms |
21828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
