//khodaya khodet komak kon
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
typedef pair <ll, ll> pll;
typedef pair <pll, pll> ppp;
# define A first
# define B second
# define endl '\n'
# define sep ' '
# define all(x) x.begin(), x.end()
# define kill(x) return cout << x << endl, 0
# define SZ(x) int(x.size())
# define lc id << 1
# define rc id << 1 | 1
# define fast_io ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
const int xn = 2e3 + 10;
const int xm = 1e5 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 998244353;
const int base = 257;
struct path{
int from, to;
ll dist = INF;
};
struct paths{
int from, to;
path a[2][2];
};
int n, m, q, L, a[xm];
ll dis[xn][xn];
priority_queue <pll> pq;
priority_queue <pair <ll, ppp> > pp;
vector <pii> adj[xn];
paths seg[xm << 2], f[xn][xn];
void dijk(int src){
for (int v = 1; v <= n; ++ v)
dis[src][v] = INF;
dis[src][src] = 0;
pq.push({0, src});
while (SZ(pq)){
int v = pq.top().B;
pq.pop();
for (pii u : adj[v])
if (dis[src][v] + u.B < dis[src][u.A])
dis[src][u.A] = dis[src][v] + u.B, pq.push({- dis[src][u.A], u.A});
}
}
void upd_paths(paths &x, path &y){
if (y.from != x.a[0][0].from && y.dist < x.a[1][0].dist)
x.a[1][0] = y;
if (y.to != x.a[0][0].to && y.dist < x.a[0][1].dist)
x.a[0][1] = y;
if (y.from != x.a[0][0].from && y.to != x.a[0][0].to && y.dist < x.a[1][1].dist)
x.a[1][1] = y;
}
paths merge(paths &x, paths &y){
paths z;
for (int i = 0; i < 2; ++ i){
for (int j = 0; j < 2; ++ j){
for (int k = 0; k < 2; ++ k){
for (int o = 0; o < 2; ++ o){
if (x.a[i][j].dist == INF || y.a[k][o].dist == INF || x.a[i][j].to == y.a[k][o].from)
continue;
path p;
p.from = x.a[i][j].from;
p.to = y.a[k][o].to;
p.dist = x.a[i][j].dist + y.a[k][o].dist;
if (p.dist < z.a[0][0].dist)
z.a[0][0] = p;
}
}
}
}
for (int i = 0; i < 2; ++ i){
for (int j = 0; j < 2; ++ j){
for (int k = 0; k < 2; ++ k){
for (int o = 0; o < 2; ++ o){
if (x.a[i][j].dist == INF || y.a[k][o].dist == INF || x.a[i][j].to == y.a[k][o].from)
continue;
path p;
p.from = x.a[i][j].from;
p.to = y.a[k][o].to;
p.dist = x.a[i][j].dist + y.a[k][o].dist;
upd_paths(z, p);
}
}
}
}
return z;
}
void build(int id, int l, int r){
if (r - l == 1){
seg[id] = f[a[l]][a[r]];
return;
}
int mid = l + r >> 1;
build(lc, l, mid);
build(rc, mid, r);
seg[id] = merge(seg[lc], seg[rc]);
}
void modify(int id, int l, int r, int pos){
if (r - l == 1){
seg[id] = f[a[l]][a[r]];
return;
}
int mid = l + r >> 1;
if (pos - 1 < mid)
modify(lc, l, mid, pos);
if (mid <= pos)
modify(rc, mid, r, pos);
seg[id] = merge(seg[lc], seg[rc]);
}
int main(){
fast_io;
cin >> n >> m >> q >> L;
while (m --){
int v, u, w;
cin >> v >> u >> w;
adj[v].push_back({u, w});
adj[u].push_back({v, w});
}
for (int v = 1; v <= n; ++ v)
dijk(v);
for (int v = 1; v <= n; ++ v){
for (int u = 1; u <= n; ++ u){
if (v == u)
continue;
f[v][u].from = v;
f[v][u].to = u;
f[v][u].a[0][0].dist = dis[v][u];
f[v][u].a[0][0].from = u;
f[v][u].a[0][0].to = v;
for (pii vv : adj[v])
for (pii uu : adj[u])
if (dis[vv.A][uu.A] + vv.B + uu.B == dis[v][u])
f[v][u].a[0][0].from = vv.A, f[v][u].a[0][0].to = uu.A;
pp.push({0, {{v, u}, {0, 0}}});
}
}
while (SZ(pp)){
int v = pp.top().B.A.A;
int u = pp.top().B.A.B;
int f1 = pp.top().B.B.A;
int f2 = pp.top().B.B.B;
pp.pop();
for (pii x : adj[u]){
if (x.A == f[v][u].a[f1][f2].to || x.A == v)
continue;
path p = f[v][u].a[f1][f2];
p.to = u;
p.dist += x.B;
if (p.dist < f[v][x.A].a[f1][0].dist && p.to == f[v][x.A].a[0][0].to){
f[v][x.A].a[f1][0] = p;
pp.push({- p.dist, {{v, x.A}, {f1, 0}}});
}
if (p.dist < f[v][x.A].a[f1][1].dist && p.to != f[v][x.A].a[0][0].to){
f[v][x.A].a[f1][1] = p;
pp.push({- p.dist, {{v, x.A}, {f1, 1}}});
}
}
for (pii x : adj[v]){
if (x.A == f[v][u].a[f1][f2].from || x.A == u)
continue;
path p = f[v][u].a[f1][f2];
p.from = v;
p.dist += x.B;
if (p.dist < f[x.A][u].a[0][f2].dist && p.from == f[x.A][u].a[0][0].from){
f[x.A][u].a[0][f2] = p;
pp.push({- p.dist, {{x.A, u}, {0, f2}}});
}
if (p.dist < f[x.A][u].a[1][f2].dist && p.from != f[x.A][u].a[0][0].from){
f[x.A][u].a[1][f2] = p;
pp.push({- p.dist, {{x.A, u}, {1, f2}}});
}
}
}
for (int i = 1; i <= L; ++ i)
cin >> a[i];
build(1, 1, L);
while (q --){
int x, y;
cin >> x >> y;
a[x] = y;
modify(1, 1, L, x);
if (seg[1].a[0][0].dist < INF)
cout << seg[1].a[0][0].dist << endl;
else
cout << - 1 << endl;
}
return 0;
}
Compilation message
wild_boar.cpp: In function 'void build(int, int, int)':
wild_boar.cpp:113:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
113 | int mid = l + r >> 1;
| ~~^~~
wild_boar.cpp: In function 'void modify(int, int, int, int)':
wild_boar.cpp:123:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
123 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
313152 KB |
Output is correct |
| 2 |
Incorrect |
113 ms |
313160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
313152 KB |
Output is correct |
| 2 |
Incorrect |
113 ms |
313160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
313152 KB |
Output is correct |
| 2 |
Incorrect |
113 ms |
313160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
313152 KB |
Output is correct |
| 2 |
Incorrect |
113 ms |
313160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
