#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <ll,ll>
#define pll pair <ll,ll>
#define piii pair <ll,pii>
#define vi vector <ll>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
using namespace std;
const ll N = 5e5 + 5;
const ll oo = 1e17;
const ll mod = 1e9 + 7;
inline void mnmize (ll &u, ll v){
if (u > v)
u = v;
}
ll n,m,x,q,u,v,w,i,up[20][100005][6][6],j,k,g,l;
vector <pii> a[N];
ll res[6][6],nres[6][6];
void jump (ll u, ll d){
forr (l,0,18)
if ((1 << l) & d){
forf (i,0,x)
forf (j,0,x)
nres[i][j] = oo;
forf (i,0,x)
forf (j,0,x)
forf (k,0,x)
mnmize (nres[i][k],res[i][j] + up[l][u][j][k]);
swap(res,nres);
u += (1 << l);
//cout << u << " " << res[0][0] << "\n";
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> x >> n >> m >> q;
ll bl = n / x + 1;
forr (i,1,m){
cin >> u >> v >> w;
a[u].pb({v,w});
}
forr (l,0,18)
forr (i,0,bl)
forf (j,0,x)
forf (k,0,x)
up[l][i][j][k] = oo;
forr (i,0,bl)
forf (j,0,x)
for (pii v : a[i * x + j]){
mnmize (up[0][i][j][v.st % x],v.nd);
}
forr (l,1,18)
forr (i,0,bl){
ll f = i + (1 << (l - 1));
forf (j,0,x)
forf (k,0,x)
forf (g,0,x)
mnmize (up[l][i][j][g],up[l - 1][i][j][k] + up[l - 1][f][k][g]);
}
while (q--){
ll b,c;
cin >> b >> c;
memset(res,0,sizeof res);
//cout << b/x << " " << c/x << " " << b % x << " " << c % x << "\n";
jump(b/x, c/x - b/x);
if (res[b % x][c % x] < oo)
cout << res[b % x][c % x] << "\n";
else cout << "-1\n";
}
return 0;
}
/*
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
143 ms |
305748 KB |
Output is correct |
2 |
Correct |
7 ms |
49752 KB |
Output is correct |
3 |
Correct |
7 ms |
49752 KB |
Output is correct |
4 |
Correct |
7 ms |
49780 KB |
Output is correct |
5 |
Correct |
8 ms |
53852 KB |
Output is correct |
6 |
Correct |
8 ms |
53852 KB |
Output is correct |
7 |
Correct |
8 ms |
53852 KB |
Output is correct |
8 |
Correct |
103 ms |
305936 KB |
Output is correct |
9 |
Correct |
94 ms |
307028 KB |
Output is correct |
10 |
Correct |
78 ms |
303476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
76 ms |
188960 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
49752 KB |
Output is correct |
2 |
Incorrect |
7 ms |
49756 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
49752 KB |
Output is correct |
2 |
Incorrect |
7 ms |
49756 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
143 ms |
305748 KB |
Output is correct |
2 |
Correct |
7 ms |
49752 KB |
Output is correct |
3 |
Correct |
7 ms |
49752 KB |
Output is correct |
4 |
Correct |
7 ms |
49780 KB |
Output is correct |
5 |
Correct |
8 ms |
53852 KB |
Output is correct |
6 |
Correct |
8 ms |
53852 KB |
Output is correct |
7 |
Correct |
8 ms |
53852 KB |
Output is correct |
8 |
Correct |
103 ms |
305936 KB |
Output is correct |
9 |
Correct |
94 ms |
307028 KB |
Output is correct |
10 |
Correct |
78 ms |
303476 KB |
Output is correct |
11 |
Incorrect |
76 ms |
188960 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |