#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 5e4+20;
const int MAXA = 9e3+20;
const ll INF = 1e18+10;
const int LOG = 19;
const int MOD = 1e15;
const int SQRT = 450;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
void chmn(int &a, int b){
a = min(a, b);
}
int n, m, q, k;
vector<vector<int>> adj[MAXN];
vector<vector<int>> NOL;
struct seg {
vector<vector<int>> st[4*MAXN];
vector<vector<int>> mrg(vector<vector<int>> a, vector<vector<int>> b){
vector<vector<int>> ret = NOL;
for(int i=0; i<k; i++){
for(int j=0; j<k; j++){
for(int p=0; p<k; p++){
chmn(ret[i][j], a[i][p]+b[p][j]);
}
}
}
return ret;
}
void bd(int id, int l, int r){
if(l==r){
st[id] = adj[l]; return;
}
bd(lf, l, md); bd(rg, md+1, r);
st[id] = mrg(st[lf], st[rg]);
return;
}
vector<vector<int>> que(int id, int l, int r, int x, int y){
if(x<=l && r<=y) return st[id];
if(r<x || y<l) return NOL;
vector<vector<int>> le = que(lf,l,md,x,y);
vector<vector<int>> ri = que(rg,md+1,r,x,y);
if(le==NOL) return ri;
if(ri==NOL) return le;
return mrg(le, ri);
}
} A;
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> k >> n >> m >> q;
vector<int> TEM(k, INF); for(int i=0; i<k; i++) NOL.pb(TEM);
for(int i=1; i<=n; i++) adj[i] = NOL;
for(int i=1; i<=m; i++){
int x, y, w; cin >> x >> y >> w;
chmn(adj[x/k+1][x%k][y%k], w);
}
A.bd(1, 1, n);
while(q--){
int a, b; cin >> a >> b;
if((a/k+1 > b/k+1) || (a/k==b/k && a!=b)){
cout << "-1\n"; continue;
}
vector<vector<int>> ret = A.que(1,1,n,a/k+1, b/k);
// cout << q << ' ' << ret[a%k][b%k] << " pp\n";
cout << (ret[a%k][b%k]>=MOD ? -1 : ret[a%k][b%k]) << '\n';
}
}
/*
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
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
16672 KB |
Output is correct |
2 |
Incorrect |
2 ms |
6232 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
75 ms |
26916 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
6236 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
6236 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
16672 KB |
Output is correct |
2 |
Incorrect |
2 ms |
6232 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |