#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){
for(Path x : paths){
if(x.second.first == avoid.first) continue;
if(x.second.second == avoid.second) continue;
return x;
}
return new_unused();
}
OptPaths process(OptPaths cand){
sort(cand.begin(), cand.end());
OptPaths edges;
pair<int,int> x = cand[0].second;
edges.push_back(cand[0]);
pair<int,int> y;
for(int i = 0; i < cand.size(); i++){
if(cand[i].second == x) continue;
y = cand[i].second;
edges.push_back(cand[i]);
break;
}
if(edges.size() == 1){
Path q = new_unused();
y = q.second;
edges.push_back(q);
}
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());
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;
}
OptPaths edge(int id, LL cost){
OptPaths x;
x.push_back({cost, {id, id}});
return x;
}
OptPaths best_paths(int s, int t){
assert(s != t);
// start bellman-ford at s
OptPaths sssp[n];
for(int i = 0; i < m; i++){
if(a[i] == s){
sssp[b[i]] = edge(i, c[i]);
} else if(b[i] == s){
sssp[a[i]] = edge(i, c[i]);
}
}
for(int j = 0; j < 2 * n + 2; j++){
for(int i = 0; i < m; i++){
if(a[i] == s || b[i] == s) continue;
OptPaths e = edge(i, c[i]);
OptPaths x = join(sssp[a[i]], e);
x.insert(x.end(), sssp[b[i]].begin(), sssp[b[i]].end());
sssp[b[i]] = process(x);
}
for(int i = 0; i < m; i++){
if(a[i] == s || b[i] == s) continue;
OptPaths e = edge(i, c[i]);
OptPaths x = join(sssp[b[i]], e);
x.insert(x.end(), sssp[a[i]].begin(), sssp[a[i]].end());
sssp[a[i]] = process(x);
}
}
return sssp[t];
}
int main(){
cin.sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> t >> l;
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]--;
}
vector<int> plan(l);
for(int i = 0; i < l; i++){
cin >> plan[i];
plan[i]--;
}
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--;
}
/*for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cout << "paths from " << i << " to " << j << '\n';
if(i != j){
OptPaths x = best_paths(i, j);
for(auto v : x){
cout << v.second.first << " " << v.second.second << " " << v.first << '\n';
}
}
}
}*/
for(int tt = 0; tt < t; tt++){
plan[updates[tt].first] = updates[tt].second;
OptPaths route = best_paths(plan[0], plan[1]);
for(int j = 2; j < l; j++){
route = process(join(route, best_paths(plan[j-1], plan[j]) ) );
}
cout << (route[0].first < MAXD ? route[0].first : -1) << '\n';
}
}
Compilation message
wild_boar.cpp: In function 'OptPaths process(OptPaths)':
wild_boar.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < cand.size(); i++){
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
