#include <bits/stdc++.h>
using namespace std;
#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
const int MAXN = 2e3, MAXM = 4e3, MAXL = 1e5;
const i64 INF = 1e18;
int N, M, T, L;
struct edge {
int s, t, w;
} edge[MAXM];
vector<int> from[MAXN];
i64 dist[MAXM][MAXM];
list<int> undone[MAXN];
struct info {
ar<int, 4> S, T; ar<i64, 4> W;
info() {
for (int i = 0; i < 4; i++) S[i] = T[i] = -1, W[i] = INF;
}
void set(int i, int s, int t, i64 w) {
S[i] = s, T[i] = t, W[i] = w;
}
void pul(const info &a, const info &b) {
for (int i = 0; i < 4; i++) S[i] = T[i] = -1, W[i] = INF;
for (int x = 0; x < 4; x++) for (int y = 0; y < 4; y++) if ((a.T[x] ^ b.S[y] ^ 1) && a.W[x] + b.W[y] < W[0])
set(0, a.S[x], b.T[y], a.W[x] + b.W[y]);
for (int x = 0; x < 4; x++) for (int y = 0; y < 4; y++) if ((a.T[x] ^ b.S[y] ^ 1) && a.W[x] + b.W[y] < W[1] && (a.S[x] ^ S[0]) && (b.T[y] ^ T[0]))
set(1, a.S[x], b.T[y], a.W[x] + b.W[y]);
for (int x = 0; x < 4; x++) for (int y = 0; y < 4; y++) if ((a.T[x] ^ b.S[y] ^ 1) && a.W[x] + b.W[y] < W[2] && (a.S[x] ^ S[0]) && (b.T[y] == T[0]))
set(2, a.S[x], b.T[y], a.W[x] + b.W[y]);
for (int x = 0; x < 4; x++) for (int y = 0; y < 4; y++) if ((a.T[x] ^ b.S[y] ^ 1) && a.W[x] + b.W[y] < W[3] && (a.S[x] == S[0]) && (b.T[y] ^ T[0]))
set(3, a.S[x], b.T[y], a.W[x] + b.W[y]);
}
} memo[MAXN][MAXN], t;
int perm[MAXL];
struct tree {
int l, r;
tree *lc = NULL, *rc = NULL;
info x;
tree(int l, int r) : l(l), r(r) {
if (l < r) {
int m = (l + r) / 2;
lc = new tree(l, m);
rc = new tree(m + 1, r);
x.pul(lc->x, rc->x);
} else x = memo[perm[l]][perm[l + 1]];
}
void upd(int i) {
if (l == r) {
x = memo[perm[l]][perm[l + 1]];
} else {
i <= lc->r ? lc->upd(i) : rc->upd(i);
x.pul(lc->x, rc->x);
}
}
i64 qry() {
return x.W[0];
}
} *tr;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M >> T >> L;
for (int h = 0; h < M; h++) {
int i, j, w;
cin >> i >> j >> w, i--, j--;
edge[h * 2] = {i, j, w};
edge[h * 2 + 1] = {j, i, w};
from[i].push_back(h * 2);
from[j].push_back(h * 2 + 1);
}
for (int x = 0; x < M * 2; x++) {
fill(dist[x], dist[x] + M * 2, INF);
for (int i = 0; i < N; i++) exchange(undone[i], {});
for (int h = 0; h < M * 2; h++) undone[edge[h].s].push_back(h);
priority_queue<pair<i64, int>> qu;
dist[x][x] = edge[x].w;
qu.push({-dist[x][x], x});
while (sz(qu)) {
auto [d, i] = qu.top(); qu.pop();
d *= -1;
if (dist[x][i] != d) continue;
for (auto j = begin(undone[edge[i].t]); j != end(undone[edge[i].t]); )
if (*j ^ i ^ 1) {
if (dist[x][i] + edge[*j].w < dist[x][*j]) {
dist[x][*j] = dist[x][i] + edge[*j].w;
qu.push({-dist[x][*j], *j});
}
auto p = j++;
undone[edge[i].t].erase(p);
} else ++j;
}
}
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
for (int x : from[i]) for (int y : from[j]) if (dist[x][y ^ 1] < t.W[0])
t.set(0, x, y ^ 1, dist[x][y ^ 1]);
for (int x : from[i]) for (int y : from[j]) if (dist[x][y ^ 1] < t.W[1] && (x ^ t.S[0]) && (y ^ t.T[0] ^ 1))
t.set(1, x, y ^ 1, dist[x][y ^ 1]);
for (int x : from[i]) for (int y : from[j]) if (dist[x][y ^ 1] < t.W[2] && (x ^ t.S[0]) && ((y ^ 1) == t.T[0]))
t.set(2, x, y ^ 1, dist[x][y ^ 1]);
for (int x : from[i]) for (int y : from[j]) if (dist[x][y ^ 1] < t.W[3] && (x == t.S[0]) && (y ^ t.T[0] ^ 1))
t.set(3, x, y ^ 1, dist[x][y ^ 1]);
swap(memo[i][j], t);
}
for (int i = 0; i < L; i++) cin >> perm[i], perm[i]--;
tr = new tree(0, L - 2);
while (T--) {
int i, v;
cin >> i >> v, i--, v--;
perm[i] = v;
if (i) tr->upd(i - 1);
if (i < L - 1) tr->upd(i);
i64 x = tr->qry();
cout << (x == INF ? -1 : x) << endl;
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
252752 KB |
Output is correct |
| 2 |
Correct |
40 ms |
252756 KB |
Output is correct |
| 3 |
Incorrect |
40 ms |
252756 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
252752 KB |
Output is correct |
| 2 |
Correct |
40 ms |
252756 KB |
Output is correct |
| 3 |
Incorrect |
40 ms |
252756 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
252752 KB |
Output is correct |
| 2 |
Correct |
40 ms |
252756 KB |
Output is correct |
| 3 |
Incorrect |
40 ms |
252756 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
252752 KB |
Output is correct |
| 2 |
Correct |
40 ms |
252756 KB |
Output is correct |
| 3 |
Incorrect |
40 ms |
252756 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
