#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
// change if necessary
#define MAXN 2010
#define MAXL 100010
using namespace std;
struct path {
int start, end;
ll length;
path(int s, int e, ll l) : start(s), end(e), length(l) {}
path() : path(0, 0, 0) {}
};
struct min_cost {
path min[4]; // min, first diff, second diff, both diff
bool set[4];
min_cost() { memset(set, 0, sizeof set); }
};
int n, m, t, l;
int nums[MAXL];
min_cost min_dist[MAXN][MAXN];
vector<int> adj[MAXN];
vector<pair<int, ll>> edge;
bool same(int x, int y) {
return x == y || (x ^ 1) == y;
}
// segtree stuff
struct segtree {
struct node {
int l, r, sz;
vector<path> combo;
node(int l, int r, int sz) : l(l), r(r), sz(sz) {}
node() : node(0, 0, 0) {}
int size() const { return r - l + 1; }
};
static int n;
node st[4 * MAXN];
// i have no clue why this works but if i set T = path[4]
// then it is passed as a pointer instead of an array
// so i am doing this instead
template<class T>
void combo(node &ans, const vector<path> &left, const T &right) {
map<pair<int, int>, ll> m;
for (auto &p1 : left) {
for (auto &p2 : right) {
if (same(p1.end, p2.start) || p2.length == 0) continue;
pair<int, int> pp = {p1.start, p2.end};
if (!m.count(pp)) {
m[pp] = p1.length + p2.length;
} else {
m[pp] = min(m[pp], p1.length + p2.length);
}
}
}
for (auto p : m) {
ans.combo.emplace_back(p.first.first, p.first.second, p.second);
}
}
void combo(node &ans, const vector<path> &left, const vector<path> &right, int x1, int x2) {
map<pair<int, int>, ll> m;
for (auto &p1 : left) {
for (auto &p2 : right) {
for (auto &join : min_dist[x1][x2].min) {
if (same(p1.end, join.start) || same(join.end, p2.start) || join.length == 0) continue;
pair<int, int> pp = {p1.start, p2.end};
if (!m.count(pp)) {
m[pp] = p1.length + p2.length + join.length;
} else {
m[pp] = min(m[pp], p1.length + p2.length + join.length);
}
}
}
}
for (auto p : m) {
ans.combo.emplace_back(p.first.first, p.first.second, p.second);
}
}
node merge(const node &left, const node &right) {
node ans;
ans.l = left.l;
ans.r = right.r;
if (left.size() == 1) {
for (path &p : min_dist[left.l][right.r].min) {
if (p.length > 0) {
ans.combo.push_back(p);
}
}
return ans;
}
if (right.size() == 1) {
combo<path[4]>(ans, left.combo, min_dist[left.r][right.l].min);
} else {
combo(ans, left.combo, right.combo, left.r, right.l);
}
return ans;
}
void build(int v = 1, int l = 0, int r = n - 1) {
if (l == r) {
st[v] = node(nums[l], nums[l], 1);
} else {
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
st[v] = merge(st[2 * v], st[2 * v + 1]);
}
}
void upd(int x, int y, int v = 1, int l = 0, int r = n - 1) {
if (l == r) {
nums[x] = y;
st[v] = node(nums[l], nums[l], 1);
} else {
int m = (l + r) / 2;
if (x <= m) {
upd(x, y, 2 * v, l, m);
} else {
upd(x, y, 2 * v + 1, m + 1, r);
}
st[v] = merge(st[2 * v], st[2 * v + 1]);
}
}
} st;
int segtree::n = 1;
bool set_vals(int x, int y, ll cost, int first, int last) {
auto &cur = min_dist[x][y];
bool ans = false;
if (!cur.set[0]) {
cur.min[0] = path(first, last, cost);
cur.set[0] = true;
ans = true;
}
if (!cur.set[1] && !same(cur.min[0].start, first)) {
cur.min[1] = path(first, last, cost);
cur.set[1] = true;
ans = true;
}
if (!cur.set[2] && !same(cur.min[0].end, last)) {
cur.min[2] = path(first, last, cost);
cur.set[2] = true;
ans = true;
}
if (!cur.set[3] && !same(cur.min[0].start, first) && !same(cur.min[0].end, last)) {
cur.min[3] = path(first, last, cost);
cur.set[3] = true;
ans = true;
}
return ans;
}
void dijk(int x) {
// {dist, pos, first edge, last edge}
priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;
min_dist[x][x].set[0] = true;
for (int e : adj[x]) {
auto [nxt, cost] = edge[e];
pq.push({cost, nxt, e, e});
}
while (!pq.empty()) {
auto [cost, pos, first, last] = pq.top();
pq.pop();
bool res = set_vals(x, pos, cost, first, last);
if (!res) continue;
for (int e : adj[pos]) {
if (!same(e, last)) {
auto [nxt, cost2] = edge[e];
pq.push({cost + cost2, nxt, first, e});
}
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> t >> l;
for (int i = 0; i < m; i++) {
int a, b; ll c;
cin >> a >> b >> c;
a--; b--;
adj[a].push_back(edge.size());
edge.push_back({b, c});
adj[b].push_back(edge.size());
edge.push_back({a, c});
}
for (int i = 0; i < n; i++) {
dijk(i);
}
for (int i = 0; i < l; i++) {
cin >> nums[i];
nums[i]--;
}
segtree::n = l;
st.build();
for (int i = 0; i < t; i++) {
int p, q; cin >> p >> q;
p--; q--;
st.upd(p, q);
if (st.st[1].combo.empty()) {
cout << "-1\n";
} else {
ll ans = INFLL;
for (auto &p : st.st[1].combo) {
ans = min(ans, p.length);
}
cout << ans << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
285420 KB |
Output is correct |
| 2 |
Correct |
177 ms |
285440 KB |
Output is correct |
| 3 |
Incorrect |
176 ms |
285420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
285420 KB |
Output is correct |
| 2 |
Correct |
177 ms |
285440 KB |
Output is correct |
| 3 |
Incorrect |
176 ms |
285420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
285420 KB |
Output is correct |
| 2 |
Correct |
177 ms |
285440 KB |
Output is correct |
| 3 |
Incorrect |
176 ms |
285420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
285420 KB |
Output is correct |
| 2 |
Correct |
177 ms |
285440 KB |
Output is correct |
| 3 |
Incorrect |
176 ms |
285420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
