#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using T = array<long long, 3>;
const int N = 2e3 + 5, K = 1e5 + 5;
const long long inf = 1e18;
int n, m, t, k;
int x[K];
array<T, 4> d[N][N], s[4 * K];
vector<array<int, 2>> g[N];
void opt(array<T, 4> &buc, vector<T> cands) {
for (int i = 0; i < 4; ++i) {
buc[i] = {inf, -1, -1};
}
for (auto p : cands) {
buc[0] = min(buc[0], p);
}
for (auto p : cands) {
if (p[0] != buc[0][0] && p[1] != buc[0][1]) {
buc[1] = min(buc[1], p);
}
}
for (auto p : cands) {
if (p[0] != buc[0][0] && p[1] != buc[1][1]) {
buc[2] = min(buc[2], p);
}
if (p[0] != buc[1][0] && p[1] != buc[0][1]) {
buc[3] = min(buc[3], p);
}
}
}
bool add(array<T, 4> &buc, T cands) {
vector<T> nw;
for (int i = 0; i < 4; ++i) {
if (buc[i][0] != inf) {
nw.push_back(buc[i]);
}
}
nw.push_back(cands);
opt(buc, nw);
for (auto x : buc) {
if (x == cands) {
return 1;
}
}
return 0;
}
void dijkstra(int src, array<T, 4> *d) {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 4; ++j) {
d[i][j] = {inf, -1, -1};
}
}
using dat = array<long long, 4>;
priority_queue<dat, vector<dat>, greater<dat>> pq;
for (auto [j, c] : g[src]) {
pq.push({c, j, j, src});
}
while (pq.size()) {
auto [c, u, s, t] = pq.top(); pq.pop();
if (!add(d[u], {c, s, t})) {
continue;
}
for (auto [v, w] : g[u]) {
if (v != t) {
pq.push({c + w, v, s, u});
}
}
}
}
void pul(int id) {
vector<T> cands;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
if (s[id * 2][i][2] != s[id * 2 + 1][j][1]) {
cands.push_back({s[id * 2][i][0] + s[id * 2 + 1][j][0], s[id * 2][i][1], s[id * 2 + 1][j][2]});
}
}
}
opt(s[id], cands);
vector<T>().swap(cands);
}
void bld(int id = 1, int l = 1, int r = k - 1) {
if (l == r) {
int u = x[l], v = x[l + 1];
opt(s[id], {d[u][v][0], d[u][v][1], d[u][v][2], d[u][v][3]});
return;
}
int md = (l + r) / 2;
bld(id * 2, l, md);
bld(id * 2 + 1, md + 1, r);
pul(id);
}
void upd(int i, int id = 1, int l = 1, int r = k - 1) {
if (l == r) {
int u = x[l], v = x[l + 1];
opt(s[id], vector<T>{d[u][v][0], d[u][v][1], d[u][v][2], d[u][v][3]});
return;
}
int md = (l + r) / 2;
if (i <= md) {
upd(i, id * 2, l, md);
} else {
upd(i, id * 2 + 1, md + 1, r);
}
pul(id);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> t >> k;
while (m--) {
int a, b, c; cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
}
for (int i = 1; i <= n; ++i) {
dijkstra(i, d[i]);
}
for (int i = 1; i <= k; ++i) {
cin >> x[i];
}
bld();
while (t--) {
int p, q; cin >> p >> q;
x[p] = q;
if (p > 1) {
upd(p - 1);
}
if (p < n) {
upd(p);
}
long long res = inf;
for (auto p : s[1]) {
res = min(res, p[0]);
}
cout << (res == inf ? -1 : res) << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
