#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();
}
int np = 0;
OptPaths process(OptPaths cand){
np++;
OptPaths edges;
if(cand.size() == 0) return edges;
sort(cand.begin(), cand.end());
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());
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;
}
OptPaths edge(int id, LL cost){
OptPaths x;
x.push_back({cost, {id, id}});
return x;
}
vector<vector<OptPaths> > cachedpaths;
void compute_paths(int s){
// start bellman-ford at s
vector<OptPaths> sssp(n);
vector<vector<int> > adj(n); // to, id, cost
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]);
} else {
adj[a[i]].push_back(i);
adj[b[i]].push_back(i);
}
}
int vis[n][4];
for(int i = 0; i < n; i++){
for(int j = 0; j < 4; j++){
vis[i][j] = 0;
}
}
set<pair<LL,pair<int,int> > > stuff;
for(int i = 0; i < n; i++){
for(int idx = 0; idx < sssp[i].size(); idx++){
stuff.insert({sssp[i][idx].first, {i, idx}});
break;
}
}
while(!stuff.empty()){
pair<LL,pair<int,int> > v = *stuff.begin();
if(v.first >= MAXD){
break;
}
stuff.erase(stuff.begin());
vis[v.second.first][v.second.second] = 1;
if(v.second.second + 1 < sssp[v.second.first].size()){
stuff.insert({sssp[v.second.first][v.second.second + 1].first, {v.second.first, v.second.second + 1}});
}
for(auto i : adj[v.second.first]){
if(b[i] == v.second.first){
swap(a[i], b[i]);
}
int w = b[i];
OptPaths e = edge(i, c[i]);
OptPaths x = join(sssp[a[i]], e);
x.insert(x.end(), sssp[w].begin(), sssp[w].end());
for(int idx = 0; idx < sssp[w].size(); idx++){
if(!vis[w][idx]){
stuff.erase({sssp[w][idx].first, {w, idx}});
break;
}
}
sssp[w] = process(x);
for(int idx = 0; idx < sssp[w].size(); idx++){
if(!vis[w][idx]){
stuff.insert({sssp[w][idx].first, {w, idx}});
break;
}
}
}
}
cachedpaths[s] = sssp;
}
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);
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++){
if(need[i]) compute_paths(i);
//cout << "done " << i << endl;
/*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';
}
}
}*/
}
//cout << np << endl;
for(int tt = 0; tt < t; tt++){
plan[updates[tt].first] = updates[tt].second;
OptPaths route = cachedpaths[plan[0]][plan[1]];
for(int j = 2; j < l; j++){
route = process(join(route, cachedpaths[plan[j-1]][plan[j]] ) );
}
//cout << (route.size() > 0 && route[0].first < MAXD ? route[0].first : -1) << '\n';
}
cout << np << endl;
}
Compilation message
wild_boar.cpp: In function 'OptPaths process(OptPaths)':
wild_boar.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < cand.size(); i++){
~~^~~~~~~~~~~~~
wild_boar.cpp: In function 'void compute_paths(int)':
wild_boar.cpp:106:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int idx = 0; idx < sssp[i].size(); idx++){
~~~~^~~~~~~~~~~~~~~~
wild_boar.cpp:118:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(v.second.second + 1 < sssp[v.second.first].size()){
~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:129:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int idx = 0; idx < sssp[w].size(); idx++){
~~~~^~~~~~~~~~~~~~~~
wild_boar.cpp:136:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int idx = 0; idx < sssp[w].size(); idx++){
~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
