#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
vector<pair<int, int>> adj0[6060];
pair<int, int> Edge[2020];
ll dist0[4040][4040], res0[4040];
int visited0[6060], F[2020];
ll (*dist)[4040];
vector<int> in[2020], out[2020];
int X[100100];
ll dp[100100][4];
struct Node{
ll W[4][4];
int S[4], E[4];
Node(){}
ll ans(){
ll ret = INF;
for (int i=0;i<4;i++){
for (int j=0;j<4;j++){
ret = min(ret, W[i][j]);
}
}
return ret==INF?-1:ret;
}
Node operator + (const Node &N) const{
Node ret;
for (int i=0;i<4;i++){
ret.S[i] = S[i];
ret.E[i] = N.E[i];
for (int j=0;j<4;j++){
ret.W[i][j] = INF;
for (int k1=0;k1<4;k1++){
for (int k2=0;k2<4;k2++) if (abs(E[k1])!=abs(N.S[k2])){
ret.W[i][j] = min(ret.W[i][j], W[i][k1] + N.W[k2][j]);
}
}
}
}
return ret;
}
};
Node initW(int p);
struct Seg{
Node tree[400400];
void init(int i, int l, int r){
if (l==r){
tree[i] = initW(l);
return;
}
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
void update(int i, int l, int r, int p){
if (r<p || p<l) return;
if (l==r){
tree[i] = initW(l);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, p); update(i<<1|1, m+1, r, p);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
}tree;
void dijkstra(int m, int s, ll (*dist)[4040], ll *res, vector<pair<int, int>> *adj){
int *visited = visited0 + 2020;
fill(res-2020, res+2020, INF);
fill(visited-2020, visited+4040, -1);
priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
vector<array<ll, 3>> st;
res[s] = F[abs(s)];
pq.push({F[abs(s)], s, 0});
// printf("dijkstra from %d:\n", s);
while(!pq.empty() || !st.empty()){
array<ll, 3> tmp;
if (!st.empty()) {tmp = st.back(); st.pop_back();}
else {tmp = pq.top(); pq.pop();}
auto [dist, cur, p] = tmp;
if (visited[cur]==-2) continue;
if (visited[cur]==-1){
if (cur <= m){
// printf(" dist[%lld] = %lld\n", cur, res[cur]);
visited[cur] = -2;
for (auto &[v, w]:adj[cur]) if (visited[v]!=-2){
st.push_back({dist, v, cur});
}
}
else{
visited[cur] = abs(p);
for (auto &[v, w]:adj[cur]) if (visited[v]!=-2 && abs(v)!=abs(p)){
res[v] = dist + w;
pq.push({res[v], v, cur});
}
}
}
else{
for (auto &[v, w]:adj[cur]) if (abs(v)==visited[cur] && visited[v]!=-2){
res[v] = dist + w;
pq.push({res[v], v, cur});
}
visited[cur] = -2;
}
}
}
map<int, Node> mp[2020];
Node initW(int p){
vector<ll> W;
vector<int> S, E;
if (mp[X[p]].find(X[p+1])!=mp[X[p]].end()){
return mp[X[p]][X[p+1]];
}
W.push_back(INF);
S.push_back(-1);
E.push_back(-1);
for (auto &s1:out[X[p]]){
for (auto &e1:in[X[p+1]]){
if (W.back() > dist[s1][e1]){
W.back() = dist[s1][e1];
S.back() = s1;
E.back() = e1;
}
}
}
W.push_back(INF);
S.push_back(-1);
E.push_back(-1);
for (auto &s2:out[X[p]]) if (s2!=S[0]){
for (auto &e2:in[X[p+1]]) if (e2!=E[0]){
if (W.back() > dist[s2][e2]){
W.back() = dist[s2][e2];
S.back() = s2;
E.back() = e2;
}
}
}
W.push_back(INF);
S.push_back(-1);
E.push_back(-1);
for (auto &s3:out[X[p]]) if (s3!=S[0]){
for (auto &e3:in[X[p+1]]) if (e3!=E[1]){
if (W.back() > dist[s3][e3]){
W.back() = dist[s3][e3];
S.back() = s3;
E.back() = e3;
}
}
}
W.push_back(INF);
S.push_back(-1);
E.push_back(-1);
for (auto &s4:out[X[p]]) if (s4!=S[1]){
for (auto &e4:in[X[p+1]]) if (e4!=E[0]){
if (W.back() > dist[s4][e4]){
W.back() = dist[s4][e4];
S.back() = s4;
E.back() = e4;
}
}
}
Node ret;
for (int i=0;i<4;i++){
for (int j=0;j<4;j++){
if (i!=j) ret.W[i][j] = INF;
else ret.W[i][j] = W[i];
}
ret.S[i] = S[i];
ret.E[i] = E[i];
}
mp[X[p]][X[p+1]] = ret;
return ret;
// printf("init %d to %d -> ", X[p], X[p+1]);
// for (int i=0;i<4;i++){
// printf("(%lld / %d, %d) ", W[p][i], S[p][i], E[p][i]);
// }
// printf("\n");
}
int main(){
int n, m, q, l;
scanf("%d %d %d %d", &n, &m, &q, &l);
vector<pair<int, int>> *adj = adj0 + m;
for (int i=1;i<=m;i++){
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
Edge[i] = {x, y}; F[i] = z;
adj[i].emplace_back(y+m, 0);
adj[-i].emplace_back(x+m, 0);
adj[x+m].emplace_back(i, z);
adj[y+m].emplace_back(-i, z);
out[x].push_back(i);
out[y].push_back(-i);
in[x].push_back(-i);
in[y].push_back(i);
}
dist = (ll (*)[4040])(&(dist0[2020][2020]));
ll *res = res0 + 2020;
for (int i=1;i<=m;i++){
dijkstra(m, i, dist, res, adj);
for (int j=-m;j<=m;j++) dist[i][j] = res[j];
dijkstra(m, -i, dist, res, adj);
for (int j=-m;j<=m;j++) dist[-i][j] = res[j];
}
for (int i=1;i<=l;i++) scanf("%d", X+i);
tree.init(1, 1, l-1);
while(q--){
int pp, qq;
scanf("%d %d", &pp, &qq);
X[pp] = qq;
if (pp > 1) tree.update(1, 1, l-1, pp-1);
if (pp < l) tree.update(1, 1, l-1, pp);
printf("%lld\n", tree.tree[1].ans());
}
// int pp, qq;
// scanf("%d %d", &pp, &qq);
// X[pp] = qq;
// for (int i=1;i<l;i++){
// initW(i, dist);
// for (int j=0;j<4;j++){
// dp[i+1][j] = INF;
// if (i==1) {dp[i+1][j] = W[1][j]; continue;}
// if (W[i][j]==INF) continue;
// for (int k=0;k<4;k++) if (abs(E[i-1][k])!=abs(S[i][j])){
// dp[i+1][j] = min(dp[i+1][j], dp[i][k] + W[i][j]);
// }
// }
// }
// ll rans = *min_element(dp[l], dp[l]+4);
// if (rans==INF) rans = -1;
// printf("%lld\n", rans);
}
Compilation message
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:219:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
219 | scanf("%d %d %d %d", &n, &m, &q, &l);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:224:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
224 | scanf("%d %d %d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:251:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
251 | for (int i=1;i<=l;i++) scanf("%d", X+i);
| ~~~~~^~~~~~~~~~~
wild_boar.cpp:256:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
256 | scanf("%d %d", &pp, &qq);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
724 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
1 ms |
724 KB |
Output is correct |
16 |
Correct |
1 ms |
724 KB |
Output is correct |
17 |
Correct |
1 ms |
724 KB |
Output is correct |
18 |
Correct |
1 ms |
788 KB |
Output is correct |
19 |
Correct |
1 ms |
724 KB |
Output is correct |
20 |
Correct |
1 ms |
724 KB |
Output is correct |
21 |
Correct |
1 ms |
724 KB |
Output is correct |
22 |
Correct |
1 ms |
724 KB |
Output is correct |
23 |
Correct |
1 ms |
724 KB |
Output is correct |
24 |
Correct |
1 ms |
724 KB |
Output is correct |
25 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
724 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
1 ms |
724 KB |
Output is correct |
16 |
Correct |
1 ms |
724 KB |
Output is correct |
17 |
Correct |
1 ms |
724 KB |
Output is correct |
18 |
Correct |
1 ms |
788 KB |
Output is correct |
19 |
Correct |
1 ms |
724 KB |
Output is correct |
20 |
Correct |
1 ms |
724 KB |
Output is correct |
21 |
Correct |
1 ms |
724 KB |
Output is correct |
22 |
Correct |
1 ms |
724 KB |
Output is correct |
23 |
Correct |
1 ms |
724 KB |
Output is correct |
24 |
Correct |
1 ms |
724 KB |
Output is correct |
25 |
Correct |
1 ms |
724 KB |
Output is correct |
26 |
Correct |
2 ms |
1108 KB |
Output is correct |
27 |
Correct |
82 ms |
45232 KB |
Output is correct |
28 |
Correct |
81 ms |
45176 KB |
Output is correct |
29 |
Correct |
141 ms |
49388 KB |
Output is correct |
30 |
Correct |
127 ms |
47372 KB |
Output is correct |
31 |
Correct |
103 ms |
47420 KB |
Output is correct |
32 |
Correct |
101 ms |
47416 KB |
Output is correct |
33 |
Correct |
151 ms |
51844 KB |
Output is correct |
34 |
Correct |
150 ms |
51896 KB |
Output is correct |
35 |
Correct |
97 ms |
47360 KB |
Output is correct |
36 |
Correct |
102 ms |
47316 KB |
Output is correct |
37 |
Correct |
153 ms |
51896 KB |
Output is correct |
38 |
Correct |
161 ms |
54756 KB |
Output is correct |
39 |
Correct |
103 ms |
47316 KB |
Output is correct |
40 |
Correct |
160 ms |
54860 KB |
Output is correct |
41 |
Correct |
158 ms |
54820 KB |
Output is correct |
42 |
Correct |
95 ms |
47416 KB |
Output is correct |
43 |
Correct |
159 ms |
57456 KB |
Output is correct |
44 |
Correct |
158 ms |
57504 KB |
Output is correct |
45 |
Correct |
134 ms |
59728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
724 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
1 ms |
724 KB |
Output is correct |
16 |
Correct |
1 ms |
724 KB |
Output is correct |
17 |
Correct |
1 ms |
724 KB |
Output is correct |
18 |
Correct |
1 ms |
788 KB |
Output is correct |
19 |
Correct |
1 ms |
724 KB |
Output is correct |
20 |
Correct |
1 ms |
724 KB |
Output is correct |
21 |
Correct |
1 ms |
724 KB |
Output is correct |
22 |
Correct |
1 ms |
724 KB |
Output is correct |
23 |
Correct |
1 ms |
724 KB |
Output is correct |
24 |
Correct |
1 ms |
724 KB |
Output is correct |
25 |
Correct |
1 ms |
724 KB |
Output is correct |
26 |
Correct |
2 ms |
1108 KB |
Output is correct |
27 |
Correct |
82 ms |
45232 KB |
Output is correct |
28 |
Correct |
81 ms |
45176 KB |
Output is correct |
29 |
Correct |
141 ms |
49388 KB |
Output is correct |
30 |
Correct |
127 ms |
47372 KB |
Output is correct |
31 |
Correct |
103 ms |
47420 KB |
Output is correct |
32 |
Correct |
101 ms |
47416 KB |
Output is correct |
33 |
Correct |
151 ms |
51844 KB |
Output is correct |
34 |
Correct |
150 ms |
51896 KB |
Output is correct |
35 |
Correct |
97 ms |
47360 KB |
Output is correct |
36 |
Correct |
102 ms |
47316 KB |
Output is correct |
37 |
Correct |
153 ms |
51896 KB |
Output is correct |
38 |
Correct |
161 ms |
54756 KB |
Output is correct |
39 |
Correct |
103 ms |
47316 KB |
Output is correct |
40 |
Correct |
160 ms |
54860 KB |
Output is correct |
41 |
Correct |
158 ms |
54820 KB |
Output is correct |
42 |
Correct |
95 ms |
47416 KB |
Output is correct |
43 |
Correct |
159 ms |
57456 KB |
Output is correct |
44 |
Correct |
158 ms |
57504 KB |
Output is correct |
45 |
Correct |
134 ms |
59728 KB |
Output is correct |
46 |
Correct |
131 ms |
12668 KB |
Output is correct |
47 |
Correct |
2245 ms |
169064 KB |
Output is correct |
48 |
Correct |
2198 ms |
168904 KB |
Output is correct |
49 |
Correct |
2279 ms |
169016 KB |
Output is correct |
50 |
Correct |
2270 ms |
169028 KB |
Output is correct |
51 |
Correct |
2272 ms |
168988 KB |
Output is correct |
52 |
Correct |
2425 ms |
188256 KB |
Output is correct |
53 |
Correct |
2425 ms |
188252 KB |
Output is correct |
54 |
Correct |
2460 ms |
188236 KB |
Output is correct |
55 |
Correct |
2408 ms |
188236 KB |
Output is correct |
56 |
Correct |
2444 ms |
188316 KB |
Output is correct |
57 |
Correct |
2456 ms |
188468 KB |
Output is correct |
58 |
Correct |
2423 ms |
188680 KB |
Output is correct |
59 |
Correct |
2416 ms |
188636 KB |
Output is correct |
60 |
Correct |
2355 ms |
188856 KB |
Output is correct |
61 |
Correct |
2324 ms |
188812 KB |
Output is correct |
62 |
Correct |
2240 ms |
188832 KB |
Output is correct |
63 |
Correct |
2161 ms |
188920 KB |
Output is correct |
64 |
Correct |
732 ms |
188992 KB |
Output is correct |
65 |
Correct |
733 ms |
188996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
724 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
1 ms |
724 KB |
Output is correct |
16 |
Correct |
1 ms |
724 KB |
Output is correct |
17 |
Correct |
1 ms |
724 KB |
Output is correct |
18 |
Correct |
1 ms |
788 KB |
Output is correct |
19 |
Correct |
1 ms |
724 KB |
Output is correct |
20 |
Correct |
1 ms |
724 KB |
Output is correct |
21 |
Correct |
1 ms |
724 KB |
Output is correct |
22 |
Correct |
1 ms |
724 KB |
Output is correct |
23 |
Correct |
1 ms |
724 KB |
Output is correct |
24 |
Correct |
1 ms |
724 KB |
Output is correct |
25 |
Correct |
1 ms |
724 KB |
Output is correct |
26 |
Correct |
2 ms |
1108 KB |
Output is correct |
27 |
Correct |
82 ms |
45232 KB |
Output is correct |
28 |
Correct |
81 ms |
45176 KB |
Output is correct |
29 |
Correct |
141 ms |
49388 KB |
Output is correct |
30 |
Correct |
127 ms |
47372 KB |
Output is correct |
31 |
Correct |
103 ms |
47420 KB |
Output is correct |
32 |
Correct |
101 ms |
47416 KB |
Output is correct |
33 |
Correct |
151 ms |
51844 KB |
Output is correct |
34 |
Correct |
150 ms |
51896 KB |
Output is correct |
35 |
Correct |
97 ms |
47360 KB |
Output is correct |
36 |
Correct |
102 ms |
47316 KB |
Output is correct |
37 |
Correct |
153 ms |
51896 KB |
Output is correct |
38 |
Correct |
161 ms |
54756 KB |
Output is correct |
39 |
Correct |
103 ms |
47316 KB |
Output is correct |
40 |
Correct |
160 ms |
54860 KB |
Output is correct |
41 |
Correct |
158 ms |
54820 KB |
Output is correct |
42 |
Correct |
95 ms |
47416 KB |
Output is correct |
43 |
Correct |
159 ms |
57456 KB |
Output is correct |
44 |
Correct |
158 ms |
57504 KB |
Output is correct |
45 |
Correct |
134 ms |
59728 KB |
Output is correct |
46 |
Correct |
131 ms |
12668 KB |
Output is correct |
47 |
Correct |
2245 ms |
169064 KB |
Output is correct |
48 |
Correct |
2198 ms |
168904 KB |
Output is correct |
49 |
Correct |
2279 ms |
169016 KB |
Output is correct |
50 |
Correct |
2270 ms |
169028 KB |
Output is correct |
51 |
Correct |
2272 ms |
168988 KB |
Output is correct |
52 |
Correct |
2425 ms |
188256 KB |
Output is correct |
53 |
Correct |
2425 ms |
188252 KB |
Output is correct |
54 |
Correct |
2460 ms |
188236 KB |
Output is correct |
55 |
Correct |
2408 ms |
188236 KB |
Output is correct |
56 |
Correct |
2444 ms |
188316 KB |
Output is correct |
57 |
Correct |
2456 ms |
188468 KB |
Output is correct |
58 |
Correct |
2423 ms |
188680 KB |
Output is correct |
59 |
Correct |
2416 ms |
188636 KB |
Output is correct |
60 |
Correct |
2355 ms |
188856 KB |
Output is correct |
61 |
Correct |
2324 ms |
188812 KB |
Output is correct |
62 |
Correct |
2240 ms |
188832 KB |
Output is correct |
63 |
Correct |
2161 ms |
188920 KB |
Output is correct |
64 |
Correct |
732 ms |
188992 KB |
Output is correct |
65 |
Correct |
733 ms |
188996 KB |
Output is correct |
66 |
Correct |
82 ms |
42480 KB |
Output is correct |
67 |
Correct |
920 ms |
77764 KB |
Output is correct |
68 |
Correct |
519 ms |
127648 KB |
Output is correct |
69 |
Correct |
1337 ms |
167824 KB |
Output is correct |
70 |
Correct |
2413 ms |
229508 KB |
Output is correct |
71 |
Correct |
3770 ms |
171380 KB |
Output is correct |
72 |
Correct |
3713 ms |
171364 KB |
Output is correct |
73 |
Correct |
4494 ms |
224580 KB |
Output is correct |
74 |
Correct |
4475 ms |
224564 KB |
Output is correct |
75 |
Correct |
4472 ms |
224648 KB |
Output is correct |
76 |
Correct |
3850 ms |
171392 KB |
Output is correct |
77 |
Correct |
3862 ms |
171460 KB |
Output is correct |
78 |
Correct |
3742 ms |
171352 KB |
Output is correct |
79 |
Correct |
4445 ms |
226868 KB |
Output is correct |
80 |
Correct |
4412 ms |
227840 KB |
Output is correct |
81 |
Correct |
3721 ms |
171452 KB |
Output is correct |
82 |
Correct |
4467 ms |
229044 KB |
Output is correct |
83 |
Correct |
3636 ms |
171524 KB |
Output is correct |
84 |
Correct |
3981 ms |
230216 KB |
Output is correct |
85 |
Correct |
2497 ms |
231068 KB |
Output is correct |