This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXD = (1LL << 60LL);
int n, m, t, l;
vector<int> a, b;
vector<LL> c;
typedef pair<LL, pair<int,int> > Path;
typedef vector<Path> OptPaths;
int unused = 3000;
Path new_unused(){
Path x = {MAXD, {unused,unused}};
//unused ++;
return x;
}
Path alt_path(pair<int,int> avoid, OptPaths& paths){
Path f = new_unused();
for(Path x : paths){
if(x.second.first != avoid.first && x.second.second != avoid.second){
if(x.first < f.first){
f = x;
}
}
}
return f;
}
Path alt_path2(pair<int,int> avoid, OptPaths& paths){
Path f = new_unused();
for(Path x : paths){
if(x.second.first != avoid.first || x.second.second != avoid.second){
if(x.first < f.first){
f = x;
}
}
}
return f;
}
int np = 0;
OptPaths process(OptPaths cand){
np++;
OptPaths edges;
if(cand.size() == 0) return edges;
edges.push_back(alt_path({-1, -1}, cand));
pair<int,int> x = edges[0].second;
if(edges[0].first >= MAXD) return edges;
edges.push_back(alt_path2(x, cand));
pair<int,int> y = edges[1].second;
if(edges[1].first >= MAXD) return edges;
if(x.first != y.first && x.second != y.second){
edges.push_back(alt_path({x.first, y.second}, cand));
edges.push_back(alt_path({y.first, x.second}, cand));
} else if(x.first == y.first){
Path q = alt_path({x.first, -1}, cand);
edges.push_back(q);
edges.push_back(alt_path({x.first, q.second.second}, cand));
} else if(x.second == y.second){
Path q = alt_path({-1, x.second}, cand);
edges.push_back(q);
edges.push_back(alt_path({q.second.first, x.second}, cand));
}
sort(edges.begin(), edges.end());
while(edges.size() > 0 && edges[edges.size() - 1].first >= MAXD) edges.pop_back();
return edges;
}
OptPaths join(OptPaths a, OptPaths b){
OptPaths cand;
for(auto x : a){
for(auto y : b){
if(x.second.second != y.second.first){
cand.push_back({min(x.first + y.first, MAXD), {x.second.first, y.second.second}});
}
}
}
return cand;
}
vector<vector<OptPaths> > cachedpaths;
void compute_paths2(int s){
// start bellman-ford at s
vector<OptPaths> sssp(n);
for(int id = 0; id < m; id++){
if(a[id] != s && b[id] != s) continue;
if(b[id] == s) swap(a[id], b[id]);
// all paths starting with edge id
int st = b[id];
vector<vector<int> > adj(n);
for(int i = 0; i < m; i++){
if(a[i] != s && b[i] != s){
adj[a[i]].push_back(i);
adj[b[i]].push_back(i);
}
}
int vis[n][2];
pair<LL,int> dist[n][2];
int changed[n];
for(int i = 0; i < n; i++){
changed[i] = 0;
vis[i][0] = vis[i][1] = 0;
dist[i][0] = {MAXD, -2};
dist[i][1] = {MAXD, -1};
}
dist[st][0] = {c[id], id};
dist[st][1] = {MAXD, -1};
changed[st] = 1;
set<pair<LL,int> > stuff;
for(int i = 0; i < n; i++){
if(i != s){
stuff.insert({dist[i][0].first, (i << 1)});
}
}
while(!stuff.empty()){
pair<LL,int> x = *stuff.begin();
stuff.erase(stuff.begin());
int v = x.second >> 1;
int idx = x.second & 1;
vis[v][idx] = 1;
if(!changed[v]) continue;
changed[v] = 0;
for(auto i : adj[v]){
if(b[i] == v){
swap(a[i], b[i]);
}
int w = b[i];
if(vis[w][0] && vis[w][1]) continue;
LL d = 0;
if(dist[v][0].second != i){
d = min(MAXD, dist[v][0].first + c[i]);
} else {
d = min(MAXD, dist[v][1].first + c[i]);
}
for(int j = 0; j < 2; j++){
if(!vis[w][j]){
stuff.erase({dist[w][j].first, (w << 1) ^ j});
break;
}
}
if(dist[w][0].second == i){
if(d < dist[w][0].first){
changed[w] = 1;
dist[w][0] = {d, i};
}
} else if(dist[w][1].second == i){
if(d < dist[w][1].first){
changed[w] = 1;
dist[w][1] = {d, i};
}
} else if(d < dist[w][1].first){
changed[w] = 1;
dist[w][1] = {d, i};
}
if(dist[w][0] > dist[w][1]) swap(dist[w][0], dist[w][1]);
for(int j = 0; j < 2; j++){
if(!vis[w][j]){
stuff.insert({dist[w][j].first, (w << 1) ^ j});
break;
}
}
}
}
for(int i = 0; i < n; i++){
if(i == s) continue;
sssp[i].push_back({dist[i][0].first,{id,dist[i][0].second}});
sssp[i].push_back({dist[i][1].first,{id,dist[i][1].second}});
}
}
for(int i = 0; i < n; i++){
if(i == s) continue;
sssp[i] = process(sssp[i]);
}
cachedpaths[s] = sssp;
}
vector<int> plan;
struct node {
node *l, *r;
int lidx, ridx;
OptPaths paths;
};
node * build(int l, int r){
node * f = new node();
f->lidx = l;
f->ridx = r;
if(l == r){
f->l = f->r = NULL;
f->paths = cachedpaths[plan[l]][plan[l+1]];
} else {
int m = (l + r) / 2;
f->l = build(l, m);
f->r = build(m + 1, r);
f->paths = process(join(f->l->paths, f->r->paths));
}
return f;
}
void upd(node * v, int x){
if(v == NULL) return;
if(v->ridx < x-1 || v->lidx > x) return;
if(v->lidx == v->ridx){
if(v->lidx == x-1){
v->paths = cachedpaths[plan[x-1]][plan[x]];
} else if(v->lidx == x){
v->paths = cachedpaths[plan[x]][plan[x+1]];
}
} else {
upd(v->l, x);
upd(v->r, x);
v->paths = process(join(v->l->paths, v->r->paths));
}
}
int main(){
cin.sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> t >> l;
cachedpaths.resize(n);
a.resize(m); b.resize(m); c.resize(m);
for(int i = 0; i < m; i++){
cin >> a[i] >> b[i] >> c[i];
a[i]--; b[i]--;
}
plan.resize(l);
vector<int> need(n, 0);
for(int i = 0; i < l; i++){
cin >> plan[i];
plan[i]--;
need[plan[i]] = 1;
}
vector<pair<int,int> > updates(t);
for(int i = 0; i < t; i++){
cin >> updates[i].first >> updates[i].second;
updates[i].first--; updates[i].second--;
need[updates[i].second] = 1;
}
for(int i = 0; i < n; i++){
compute_paths2(i);
//cout << "done " << i << endl;
}
node * tree = build(0, l - 2);
for(int tt = 0; tt < t; tt++){
int x = updates[tt].first;
plan[x] = updates[tt].second;
upd(tree, x);
OptPaths& route = tree->paths;
cout << (route.size() > 0 && route[0].first < MAXD ? route[0].first : -1) << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |