//______________"In The Name Of GOD"______________
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
const int lg = 20;
const int mod = 1e9 + 7;
const ll inf = 1e15 + 100;
const int maxn = 1e6 + 100;
#define cl clear
#define F first
#define S second
#define pb push_back
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
ll a[maxn], b[maxn], dp[maxn], pd[maxn], ans[maxn], n, k, bl;
vector <pii> adj[maxn], jda[maxn];
vector <int> qu[4 * maxn];
inline void avocado(int nd = 1, int s = 0, int e = bl){
if (e - s == 1) return;
int mid = (s + e) / 2, lc = 2 * nd, rc = 2 * nd + 1;
avocado(lc, s, mid), avocado(rc, mid, e);
for (int i = 0; i < k; i ++){
int v = mid * k + i;
if(v >= n) break;
fill(dp + s * k, dp + e * k, inf), fill(pd + s * k, pd + e * k, inf);
dp[v] = 0;
for (int j = v; j < k * e; j ++){
for (auto p : adj[j]){
int u = p.F, w = p.S;
dp[u] = min(dp[u], dp[j] + w);
}
}
pd[v] = 0;
for (int j = v; j >= s * k; j --){
for (auto p : jda[j]){
int u = p.F, w = p.S;
pd[u] = min(pd[u], pd[j] + w);
}
}
for (int x : qu[nd]){
ans[x] = min(ans[x], pd[a[x]] + dp[b[x]]);
}
}
return;
}
inline int find(int l, int r, int v = 1, int s = 0, int e = bl){
if(e - s == 1) return v;
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
if(r <= mid) return find(l, r, lc, s, mid);
if(mid < l) return find(l, r, rc, mid, e);
return v;
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int m, q;
cin >> k >> n >> m >> q;
bl = (n + k - 1) / k;
for (int i = 0; i < m; i ++){
int v, u, t;
cin >> v >> u >> t;
adj[v].pb({u, t});
jda[u].pb({v, t});
}
fill(ans, ans + q, inf);
for (int i = 0; i < q; i ++){
cin >> a[i] >> b[i];
if(a[i] > b[i]) continue;
qu[find(a[i] / k, b[i] / k + 1)].pb(i);
}
avocado();
for (int i = 0; i < q; i ++) cout << (ans[i] >= mod ? -1 : ans[i]) << '\n';
return 0;
}
/*test case :
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
109 ms |
145492 KB |
Output is correct |
2 |
Correct |
62 ms |
141264 KB |
Output is correct |
3 |
Correct |
64 ms |
141256 KB |
Output is correct |
4 |
Correct |
63 ms |
141188 KB |
Output is correct |
5 |
Correct |
63 ms |
141364 KB |
Output is correct |
6 |
Correct |
72 ms |
141300 KB |
Output is correct |
7 |
Correct |
71 ms |
141468 KB |
Output is correct |
8 |
Correct |
99 ms |
146420 KB |
Output is correct |
9 |
Correct |
100 ms |
146128 KB |
Output is correct |
10 |
Correct |
69 ms |
142468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
134 ms |
145564 KB |
Output is correct |
2 |
Correct |
66 ms |
141256 KB |
Output is correct |
3 |
Correct |
64 ms |
141168 KB |
Output is correct |
4 |
Correct |
64 ms |
141136 KB |
Output is correct |
5 |
Correct |
65 ms |
141260 KB |
Output is correct |
6 |
Correct |
68 ms |
141208 KB |
Output is correct |
7 |
Correct |
68 ms |
141648 KB |
Output is correct |
8 |
Correct |
71 ms |
141732 KB |
Output is correct |
9 |
Correct |
105 ms |
146368 KB |
Output is correct |
10 |
Correct |
164 ms |
148432 KB |
Output is correct |
11 |
Correct |
129 ms |
146740 KB |
Output is correct |
12 |
Correct |
129 ms |
146356 KB |
Output is correct |
13 |
Correct |
178 ms |
148384 KB |
Output is correct |
14 |
Correct |
122 ms |
146248 KB |
Output is correct |
15 |
Correct |
133 ms |
145504 KB |
Output is correct |
16 |
Correct |
144 ms |
145548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
141132 KB |
Output is correct |
2 |
Correct |
63 ms |
141260 KB |
Output is correct |
3 |
Correct |
63 ms |
141260 KB |
Output is correct |
4 |
Correct |
64 ms |
141164 KB |
Output is correct |
5 |
Correct |
66 ms |
141384 KB |
Output is correct |
6 |
Correct |
65 ms |
141232 KB |
Output is correct |
7 |
Correct |
64 ms |
141244 KB |
Output is correct |
8 |
Correct |
63 ms |
141516 KB |
Output is correct |
9 |
Correct |
65 ms |
141420 KB |
Output is correct |
10 |
Correct |
116 ms |
145984 KB |
Output is correct |
11 |
Correct |
123 ms |
146332 KB |
Output is correct |
12 |
Correct |
174 ms |
148136 KB |
Output is correct |
13 |
Correct |
174 ms |
148584 KB |
Output is correct |
14 |
Correct |
147 ms |
147360 KB |
Output is correct |
15 |
Correct |
148 ms |
145612 KB |
Output is correct |
16 |
Correct |
135 ms |
145468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
141132 KB |
Output is correct |
2 |
Correct |
63 ms |
141260 KB |
Output is correct |
3 |
Correct |
63 ms |
141260 KB |
Output is correct |
4 |
Correct |
64 ms |
141164 KB |
Output is correct |
5 |
Correct |
66 ms |
141384 KB |
Output is correct |
6 |
Correct |
65 ms |
141232 KB |
Output is correct |
7 |
Correct |
64 ms |
141244 KB |
Output is correct |
8 |
Correct |
63 ms |
141516 KB |
Output is correct |
9 |
Correct |
65 ms |
141420 KB |
Output is correct |
10 |
Correct |
116 ms |
145984 KB |
Output is correct |
11 |
Correct |
123 ms |
146332 KB |
Output is correct |
12 |
Correct |
174 ms |
148136 KB |
Output is correct |
13 |
Correct |
174 ms |
148584 KB |
Output is correct |
14 |
Correct |
147 ms |
147360 KB |
Output is correct |
15 |
Correct |
148 ms |
145612 KB |
Output is correct |
16 |
Correct |
135 ms |
145468 KB |
Output is correct |
17 |
Correct |
124 ms |
146360 KB |
Output is correct |
18 |
Correct |
64 ms |
141260 KB |
Output is correct |
19 |
Correct |
65 ms |
141224 KB |
Output is correct |
20 |
Correct |
70 ms |
141288 KB |
Output is correct |
21 |
Correct |
65 ms |
141260 KB |
Output is correct |
22 |
Correct |
63 ms |
141200 KB |
Output is correct |
23 |
Correct |
65 ms |
141444 KB |
Output is correct |
24 |
Correct |
65 ms |
141460 KB |
Output is correct |
25 |
Correct |
65 ms |
141516 KB |
Output is correct |
26 |
Correct |
75 ms |
141564 KB |
Output is correct |
27 |
Correct |
98 ms |
146100 KB |
Output is correct |
28 |
Correct |
164 ms |
148184 KB |
Output is correct |
29 |
Correct |
182 ms |
148776 KB |
Output is correct |
30 |
Correct |
164 ms |
147484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
109 ms |
145492 KB |
Output is correct |
2 |
Correct |
62 ms |
141264 KB |
Output is correct |
3 |
Correct |
64 ms |
141256 KB |
Output is correct |
4 |
Correct |
63 ms |
141188 KB |
Output is correct |
5 |
Correct |
63 ms |
141364 KB |
Output is correct |
6 |
Correct |
72 ms |
141300 KB |
Output is correct |
7 |
Correct |
71 ms |
141468 KB |
Output is correct |
8 |
Correct |
99 ms |
146420 KB |
Output is correct |
9 |
Correct |
100 ms |
146128 KB |
Output is correct |
10 |
Correct |
69 ms |
142468 KB |
Output is correct |
11 |
Correct |
134 ms |
145564 KB |
Output is correct |
12 |
Correct |
66 ms |
141256 KB |
Output is correct |
13 |
Correct |
64 ms |
141168 KB |
Output is correct |
14 |
Correct |
64 ms |
141136 KB |
Output is correct |
15 |
Correct |
65 ms |
141260 KB |
Output is correct |
16 |
Correct |
68 ms |
141208 KB |
Output is correct |
17 |
Correct |
68 ms |
141648 KB |
Output is correct |
18 |
Correct |
71 ms |
141732 KB |
Output is correct |
19 |
Correct |
105 ms |
146368 KB |
Output is correct |
20 |
Correct |
164 ms |
148432 KB |
Output is correct |
21 |
Correct |
129 ms |
146740 KB |
Output is correct |
22 |
Correct |
129 ms |
146356 KB |
Output is correct |
23 |
Correct |
178 ms |
148384 KB |
Output is correct |
24 |
Correct |
122 ms |
146248 KB |
Output is correct |
25 |
Correct |
133 ms |
145504 KB |
Output is correct |
26 |
Correct |
144 ms |
145548 KB |
Output is correct |
27 |
Correct |
63 ms |
141132 KB |
Output is correct |
28 |
Correct |
63 ms |
141260 KB |
Output is correct |
29 |
Correct |
63 ms |
141260 KB |
Output is correct |
30 |
Correct |
64 ms |
141164 KB |
Output is correct |
31 |
Correct |
66 ms |
141384 KB |
Output is correct |
32 |
Correct |
65 ms |
141232 KB |
Output is correct |
33 |
Correct |
64 ms |
141244 KB |
Output is correct |
34 |
Correct |
63 ms |
141516 KB |
Output is correct |
35 |
Correct |
65 ms |
141420 KB |
Output is correct |
36 |
Correct |
116 ms |
145984 KB |
Output is correct |
37 |
Correct |
123 ms |
146332 KB |
Output is correct |
38 |
Correct |
174 ms |
148136 KB |
Output is correct |
39 |
Correct |
174 ms |
148584 KB |
Output is correct |
40 |
Correct |
147 ms |
147360 KB |
Output is correct |
41 |
Correct |
148 ms |
145612 KB |
Output is correct |
42 |
Correct |
135 ms |
145468 KB |
Output is correct |
43 |
Correct |
124 ms |
146360 KB |
Output is correct |
44 |
Correct |
64 ms |
141260 KB |
Output is correct |
45 |
Correct |
65 ms |
141224 KB |
Output is correct |
46 |
Correct |
70 ms |
141288 KB |
Output is correct |
47 |
Correct |
65 ms |
141260 KB |
Output is correct |
48 |
Correct |
63 ms |
141200 KB |
Output is correct |
49 |
Correct |
65 ms |
141444 KB |
Output is correct |
50 |
Correct |
65 ms |
141460 KB |
Output is correct |
51 |
Correct |
65 ms |
141516 KB |
Output is correct |
52 |
Correct |
75 ms |
141564 KB |
Output is correct |
53 |
Correct |
98 ms |
146100 KB |
Output is correct |
54 |
Correct |
164 ms |
148184 KB |
Output is correct |
55 |
Correct |
182 ms |
148776 KB |
Output is correct |
56 |
Correct |
164 ms |
147484 KB |
Output is correct |
57 |
Correct |
210 ms |
148972 KB |
Output is correct |
58 |
Correct |
101 ms |
146348 KB |
Output is correct |
59 |
Correct |
138 ms |
146636 KB |
Output is correct |