#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;
if(cand.size() == 0) return 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){
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());
return edges;
}
OptPaths join(OptPaths a, OptPaths b){
assert(a.size() <= 4 && b.size() <= 4);
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;
}
vector<vector<OptPaths> > cachedpaths;
OptPaths best_paths(int s, int t){
if(cachedpaths[s].empty()){
// start bellman-ford at s
vector<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 < n; 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);
}
}
cachedpaths[s] = sssp;
}
return cachedpaths[s][t];
}
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]--;
}
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.size() > 0 && route[0].first < MAXD ? route[0].first : -1) << '\n';
}
}
Compilation message
wild_boar.cpp: In function 'OptPaths process(OptPaths)':
wild_boar.cpp:35: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 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
480 KB |
Output is correct |
4 |
Correct |
2 ms |
556 KB |
Output is correct |
5 |
Correct |
3 ms |
556 KB |
Output is correct |
6 |
Correct |
3 ms |
556 KB |
Output is correct |
7 |
Correct |
3 ms |
556 KB |
Output is correct |
8 |
Correct |
3 ms |
556 KB |
Output is correct |
9 |
Correct |
4 ms |
556 KB |
Output is correct |
10 |
Correct |
3 ms |
556 KB |
Output is correct |
11 |
Correct |
2 ms |
556 KB |
Output is correct |
12 |
Correct |
3 ms |
556 KB |
Output is correct |
13 |
Correct |
3 ms |
596 KB |
Output is correct |
14 |
Correct |
3 ms |
620 KB |
Output is correct |
15 |
Correct |
3 ms |
620 KB |
Output is correct |
16 |
Correct |
10 ms |
620 KB |
Output is correct |
17 |
Correct |
3 ms |
620 KB |
Output is correct |
18 |
Correct |
3 ms |
636 KB |
Output is correct |
19 |
Correct |
4 ms |
636 KB |
Output is correct |
20 |
Correct |
4 ms |
636 KB |
Output is correct |
21 |
Correct |
3 ms |
636 KB |
Output is correct |
22 |
Correct |
2 ms |
636 KB |
Output is correct |
23 |
Correct |
2 ms |
636 KB |
Output is correct |
24 |
Correct |
3 ms |
768 KB |
Output is correct |
25 |
Correct |
3 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
480 KB |
Output is correct |
4 |
Correct |
2 ms |
556 KB |
Output is correct |
5 |
Correct |
3 ms |
556 KB |
Output is correct |
6 |
Correct |
3 ms |
556 KB |
Output is correct |
7 |
Correct |
3 ms |
556 KB |
Output is correct |
8 |
Correct |
3 ms |
556 KB |
Output is correct |
9 |
Correct |
4 ms |
556 KB |
Output is correct |
10 |
Correct |
3 ms |
556 KB |
Output is correct |
11 |
Correct |
2 ms |
556 KB |
Output is correct |
12 |
Correct |
3 ms |
556 KB |
Output is correct |
13 |
Correct |
3 ms |
596 KB |
Output is correct |
14 |
Correct |
3 ms |
620 KB |
Output is correct |
15 |
Correct |
3 ms |
620 KB |
Output is correct |
16 |
Correct |
10 ms |
620 KB |
Output is correct |
17 |
Correct |
3 ms |
620 KB |
Output is correct |
18 |
Correct |
3 ms |
636 KB |
Output is correct |
19 |
Correct |
4 ms |
636 KB |
Output is correct |
20 |
Correct |
4 ms |
636 KB |
Output is correct |
21 |
Correct |
3 ms |
636 KB |
Output is correct |
22 |
Correct |
2 ms |
636 KB |
Output is correct |
23 |
Correct |
2 ms |
636 KB |
Output is correct |
24 |
Correct |
3 ms |
768 KB |
Output is correct |
25 |
Correct |
3 ms |
768 KB |
Output is correct |
26 |
Correct |
29 ms |
768 KB |
Output is correct |
27 |
Correct |
1665 ms |
2256 KB |
Output is correct |
28 |
Correct |
2079 ms |
2256 KB |
Output is correct |
29 |
Correct |
6043 ms |
2256 KB |
Output is correct |
30 |
Correct |
683 ms |
2256 KB |
Output is correct |
31 |
Correct |
245 ms |
2256 KB |
Output is correct |
32 |
Correct |
323 ms |
2256 KB |
Output is correct |
33 |
Correct |
12713 ms |
3504 KB |
Output is correct |
34 |
Correct |
12850 ms |
3508 KB |
Output is correct |
35 |
Correct |
240 ms |
3508 KB |
Output is correct |
36 |
Correct |
372 ms |
3508 KB |
Output is correct |
37 |
Correct |
12638 ms |
3524 KB |
Output is correct |
38 |
Execution timed out |
18104 ms |
4760 KB |
Time limit exceeded |
39 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
480 KB |
Output is correct |
4 |
Correct |
2 ms |
556 KB |
Output is correct |
5 |
Correct |
3 ms |
556 KB |
Output is correct |
6 |
Correct |
3 ms |
556 KB |
Output is correct |
7 |
Correct |
3 ms |
556 KB |
Output is correct |
8 |
Correct |
3 ms |
556 KB |
Output is correct |
9 |
Correct |
4 ms |
556 KB |
Output is correct |
10 |
Correct |
3 ms |
556 KB |
Output is correct |
11 |
Correct |
2 ms |
556 KB |
Output is correct |
12 |
Correct |
3 ms |
556 KB |
Output is correct |
13 |
Correct |
3 ms |
596 KB |
Output is correct |
14 |
Correct |
3 ms |
620 KB |
Output is correct |
15 |
Correct |
3 ms |
620 KB |
Output is correct |
16 |
Correct |
10 ms |
620 KB |
Output is correct |
17 |
Correct |
3 ms |
620 KB |
Output is correct |
18 |
Correct |
3 ms |
636 KB |
Output is correct |
19 |
Correct |
4 ms |
636 KB |
Output is correct |
20 |
Correct |
4 ms |
636 KB |
Output is correct |
21 |
Correct |
3 ms |
636 KB |
Output is correct |
22 |
Correct |
2 ms |
636 KB |
Output is correct |
23 |
Correct |
2 ms |
636 KB |
Output is correct |
24 |
Correct |
3 ms |
768 KB |
Output is correct |
25 |
Correct |
3 ms |
768 KB |
Output is correct |
26 |
Correct |
29 ms |
768 KB |
Output is correct |
27 |
Correct |
1665 ms |
2256 KB |
Output is correct |
28 |
Correct |
2079 ms |
2256 KB |
Output is correct |
29 |
Correct |
6043 ms |
2256 KB |
Output is correct |
30 |
Correct |
683 ms |
2256 KB |
Output is correct |
31 |
Correct |
245 ms |
2256 KB |
Output is correct |
32 |
Correct |
323 ms |
2256 KB |
Output is correct |
33 |
Correct |
12713 ms |
3504 KB |
Output is correct |
34 |
Correct |
12850 ms |
3508 KB |
Output is correct |
35 |
Correct |
240 ms |
3508 KB |
Output is correct |
36 |
Correct |
372 ms |
3508 KB |
Output is correct |
37 |
Correct |
12638 ms |
3524 KB |
Output is correct |
38 |
Execution timed out |
18104 ms |
4760 KB |
Time limit exceeded |
39 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
480 KB |
Output is correct |
4 |
Correct |
2 ms |
556 KB |
Output is correct |
5 |
Correct |
3 ms |
556 KB |
Output is correct |
6 |
Correct |
3 ms |
556 KB |
Output is correct |
7 |
Correct |
3 ms |
556 KB |
Output is correct |
8 |
Correct |
3 ms |
556 KB |
Output is correct |
9 |
Correct |
4 ms |
556 KB |
Output is correct |
10 |
Correct |
3 ms |
556 KB |
Output is correct |
11 |
Correct |
2 ms |
556 KB |
Output is correct |
12 |
Correct |
3 ms |
556 KB |
Output is correct |
13 |
Correct |
3 ms |
596 KB |
Output is correct |
14 |
Correct |
3 ms |
620 KB |
Output is correct |
15 |
Correct |
3 ms |
620 KB |
Output is correct |
16 |
Correct |
10 ms |
620 KB |
Output is correct |
17 |
Correct |
3 ms |
620 KB |
Output is correct |
18 |
Correct |
3 ms |
636 KB |
Output is correct |
19 |
Correct |
4 ms |
636 KB |
Output is correct |
20 |
Correct |
4 ms |
636 KB |
Output is correct |
21 |
Correct |
3 ms |
636 KB |
Output is correct |
22 |
Correct |
2 ms |
636 KB |
Output is correct |
23 |
Correct |
2 ms |
636 KB |
Output is correct |
24 |
Correct |
3 ms |
768 KB |
Output is correct |
25 |
Correct |
3 ms |
768 KB |
Output is correct |
26 |
Correct |
29 ms |
768 KB |
Output is correct |
27 |
Correct |
1665 ms |
2256 KB |
Output is correct |
28 |
Correct |
2079 ms |
2256 KB |
Output is correct |
29 |
Correct |
6043 ms |
2256 KB |
Output is correct |
30 |
Correct |
683 ms |
2256 KB |
Output is correct |
31 |
Correct |
245 ms |
2256 KB |
Output is correct |
32 |
Correct |
323 ms |
2256 KB |
Output is correct |
33 |
Correct |
12713 ms |
3504 KB |
Output is correct |
34 |
Correct |
12850 ms |
3508 KB |
Output is correct |
35 |
Correct |
240 ms |
3508 KB |
Output is correct |
36 |
Correct |
372 ms |
3508 KB |
Output is correct |
37 |
Correct |
12638 ms |
3524 KB |
Output is correct |
38 |
Execution timed out |
18104 ms |
4760 KB |
Time limit exceeded |
39 |
Halted |
0 ms |
0 KB |
- |