#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define ll long long
const int N=2005;
const int M=200050;
const int C=4;
const ll inf=4e18;
struct path{
int u,v;ll cost;
path(int a=0,int b=0,ll c=inf):u(a),v(b),cost(c){}
};
bool operator < (path a,path b){return a.cost>b.cost;}
path dist[N][N][C];
bool push(path tmp[C],path now){
int i,c1=0,c2=0;
for(i=0;i<C&&tmp[i].cost<now.cost;i++){
if(tmp[i].u==now.u&&tmp[i].v==now.v)return 0;
c1+=tmp[i].u==now.u;
c2+=tmp[i].v==now.v;
}
if(c1>1||c2>1||i==C)return 0;
tmp[i]=now;
return 1;
}
vector<pii> E[N];
int ls[M],rs[M],tsz,root;
path node[M][C];
void pull(int c){
for(int i=0;i<C;i++)node[c][i]=path();
vector<path> tmp;
for(int j=0;j<C;j++)
for(int k=0;k<C;k++)
if(node[ls[c]][j].v!=node[rs[c]][k].u)
tmp.pb(path(node[ls[c]][j].u,node[rs[c]][k].v,node[ls[c]][j].cost+node[rs[c]][k].cost));
sort(tmp.begin(),tmp.end());
while(tmp.size())push(node[c],tmp.back()),tmp.pop_back();
}
int x[M];
void Set(int&c,int ss,int se,int qi){
if(!c)c=++tsz;
if(ss==se){
for(int i=0;i<C;i++)node[c][i]=dist[x[ss]][x[ss+1]][i];
return;
}
int mid=ss+se>>1;
if(qi<=mid)Set(ls[c],ss,mid,qi);
else Set(rs[c],mid+1,se,qi);
pull(c);
}
int main(){
int n,m,t,l;
scanf("%i %i %i %i",&n,&m,&t,&l);
for(int i=1,u,v,w;i<=m;i++)scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w});
for(int u=1;u<=n;u++){
priority_queue<pair<path,int>> pq;
for(auto e:E[u])pq.push({path(e.first,u,e.second),e.first});
while(pq.size()){
pair<path,int> now=pq.top();
pq.pop();
if(!push(dist[u][now.second],now.first))continue;
for(auto e:E[now.second])if(e.first!=now.first.v)
pq.push({path(now.first.u,now.second,now.first.cost+e.second),e.first});
}
}
for(int i=1;i<=l;i++)scanf("%i",&x[i]);
for(int i=1;i<l;i++)Set(root,1,l-1,i);
while(t--){
int i,y;
scanf("%i %i",&i,&y);
x[i]=y;
if(i!=1)Set(root,1,l-1,i-1);
if(i!=l)Set(root,1,l-1,i);
ll ans=node[root][0].cost;
printf("%lld\n",ans<inf?ans:-1);
}
return 0;
}
Compilation message
wild_boar.cpp: In function 'void Set(int&, int, int, int)':
wild_boar.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mid=ss+se>>1;
| ~~^~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
54 | scanf("%i %i %i %i",&n,&m,&t,&l);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:55:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
55 | for(int i=1,u,v,w;i<=m;i++)scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w});
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:67:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
67 | for(int i=1;i<=l;i++)scanf("%i",&x[i]);
| ~~~~~^~~~~~~~~~~~
wild_boar.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
71 | scanf("%i %i",&i,&y);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
264568 KB |
Output is correct |
| 2 |
Correct |
155 ms |
264568 KB |
Output is correct |
| 3 |
Incorrect |
154 ms |
264696 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
264568 KB |
Output is correct |
| 2 |
Correct |
155 ms |
264568 KB |
Output is correct |
| 3 |
Incorrect |
154 ms |
264696 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
264568 KB |
Output is correct |
| 2 |
Correct |
155 ms |
264568 KB |
Output is correct |
| 3 |
Incorrect |
154 ms |
264696 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
264568 KB |
Output is correct |
| 2 |
Correct |
155 ms |
264568 KB |
Output is correct |
| 3 |
Incorrect |
154 ms |
264696 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
