#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;
template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }
const LL infLL = 1e18;
mt19937 rng( (int)chrono::steady_clock::now().time_since_epoch().count() );
int n, nDay, nSta;
struct Edge {
int from, to, w;
Edge(int _from, int _to, int _w) : from(_from), to(_to), w(_w) {}
};
vector<Edge> edge;
vector<vector<int> > gr;
vector<vector<LL> > d;
void dijkstra(int s) {
d[s][s] = edge[s].w;
priority_queue<pair<LL, int>, vector<pair<LL, int> >, greater<pair<LL, int> > > pq;
pq.emplace(-d[s][s], s);
while (sz(pq) ) {
LL curD = -pq.top().first; int u = pq.top().second; pq.pop();
if (curD ^ d[s][u]) continue ;
for (int v : gr[edge[u].to]) if ( (u >> 1) ^ (v >> 1) ) {
if (asMn(d[s][v], curD + edge[v].w) ) pq.emplace(-d[s][v], v);
}
}
}
vector<vector<vector<pair<int, int> > > > optimalE;
vector<int> x;
struct It {
#define lC (i << 1)
#define rC (i << 1 | 1)
#define Mid ( (Left + Right) >> 1)
#define rt int i = 1, int Left = 0, int Right = nSta - 2
struct Node {
map<pair<int, int>, LL> val;
Node() { val.clear(); }
Node operator + (const Node &_) const {
Node ret;
for (auto i : val) {
for (auto j : _.val) if ( (i.first.second >> 1) ^ (j.first.first >> 1) ) {
if (ret.val.count(make_pair(i.first.first, j.first.second) ) ) asMn(ret.val[make_pair(i.first.first, j.first.second)], i.second + j.second);
else ret.val[make_pair(i.first.first, j.first.second)] = i.second + j.second;
}
}
return ret;
}
};
vector<Node> node;
It(int nNode) { node.assign(nNode, Node() ); }
void build(rt) {
if (!(Left ^ Right) ) {
for (auto _ : optimalE[ x[Left] ][ x[Left + 1] ]) if (_ != make_pair(-1, -1) ) node[i].val[_] = d[_.first][_.second];
return ;
}
build(lC, Left, Mid);
build(rC, Mid + 1, Right);
node[i] = node[lC] + node[rC];
}
void upd(int pos, rt) {
if (Left == Right) {
node[i].val.clear();
for (auto _ : optimalE[ x[Left] ][ x[Left + 1] ]) if (_ != make_pair(-1, -1) ) node[i].val[_] = d[_.first][_.second];
return ;
}
if (pos <= Mid) upd(pos, lC, Left, Mid);
else upd(pos, rC, Mid + 1, Right);
node[i] = node[lC] + node[rC];
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef FourLeafClover
freopen("input", "r", stdin);
#endif // FourLeafClover
int m; cin >> n >> m >> nDay >> nSta;
gr.assign(n, {} );
while (m--) {
int u, v, w; cin >> u >> v >> w; --u; --v;
gr[u].emplace_back(sz(edge) ); edge.emplace_back(u, v, w);
gr[v].emplace_back(sz(edge) ); edge.emplace_back(v, u, w);
}
d.assign(sz(edge), vector<LL>(sz(edge), infLL) );
for (int s = 0; s < sz(edge); ++s) dijkstra(s);
optimalE.assign(n, vector<vector<pair<int, int> > >(n) );
for (int from = 0; from < n; ++from) {
for (int to = 0; to < n; ++to) if (from ^ to) {
optimalE[from][to].emplace_back(-1, -1);
LL mn = infLL;
for (int s : gr[from]) {
for (int t : gr[to]) if (asMn(mn, d[s][t ^ 1]) ) optimalE[from][to].back() = { s, t ^ 1 };
}
optimalE[from][to].emplace_back(-1, -1);
mn = infLL;
for (int s : gr[from]) if (s ^ optimalE[from][to][0].first) {
for (int t : gr[to]) if (asMn(mn, d[s][t ^ 1]) ) optimalE[from][to].back() = { s, t ^ 1 };
}
optimalE[from][to].emplace_back(-1, -1);
mn = infLL;
for (int s : gr[from]) if (s ^ optimalE[from][to][0].first) {
for (int t : gr[to]) if (t ^ 1 ^ optimalE[from][to].back().second && asMn(mn, d[s][t ^ 1]) ) optimalE[from][to].back() = { s, t ^ 1 };
}
optimalE[from][to].emplace_back(-1, -1);
mn = infLL;
for (int s : gr[from]) {
for (int t : gr[to]) if (t ^ 1 ^ optimalE[from][to][0].second && asMn(mn, d[s][t ^ 1]) ) optimalE[from][to].back() = { s, t ^ 1 };
}
optimalE[from][to].emplace_back(-1, -1);
mn = infLL;
for (int s : gr[from]) if (s ^ optimalE[from][to].back().first) {
for (int t : gr[to]) if (t ^ 1 ^ optimalE[from][to][0].second && asMn(mn, d[s][t ^ 1]) ) optimalE[from][to].back() = { s, t ^ 1 };
}
}
}
x.assign(nSta, 0);
for (auto &i : x) cin >> i, --i;
It it( (nSta + 5) << 2); it.build();
while (nDay--) {
int p, v; cin >> p >> v; --p; --v;
x[p] = v;
if (p) it.upd(p - 1);
if (p + 1 < nSta) it.upd(p);
LL ans = infLL;
for (auto _ : it.node[1].val) asMn(ans, _.second);
cout << (ans ^ infLL ? ans : -1) << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
