#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, N=2005, M=4005;
typedef array<pair<ll, pii>, 5> DATA;
int n, m, T, L, k, u, v, x, y, t, a, b, ans;
int U[M], V[M], W[M], X[MAXN];
ll dist[M][M];
bool mark[M][M];
DATA F[N][N];
DATA seg[MAXN<<2];
vector<int> G[N];
priority_queue<pll, vector<pll>, greater<pll>> pq;
DATA Merge(DATA X, DATA Y){
vector<pair<ll, pii>> vec;
for (int i=0; i<5; i++) for (int j=0; j<5; j++) if (X[i].first+Y[j].first<INF && X[i].second.second!=Y[j].second.first){
int a=X[i].second.first, b=Y[j].second.second;
ll w=X[i].first+Y[j].first;
vec.pb({w, {a, b}});
}
DATA Z=F[0][0];
sort(all(vec));
if (vec.empty()) return Z;
Z[0]=vec[0];
int sz=1, lastx=-1, lasty=-1, tedx=0, tedy=0;
int x=Z[0].second.first, y=Z[0].second.second;
for (int i=1; i<vec.size() && sz<5; i++){
int a=vec[i].second.first, b=vec[i].second.second;
bool okx=(a!=x && b!=lastx && tedx<2);
bool oky=(b!=y && a!=lasty && tedy<2);
if (okx){
Z[sz++]=vec[i];
tedx++;
lastx=b;
}
else if (oky){
Z[sz++]=vec[i];
tedy++;
lasty=a;
}
}
return Z;
}
void print(DATA X){
for (int i=0; i<5 && X[i].first<INF; i++) cerr<<"{"<<X[i].first<<", ("<<X[i].second.first<<", "<<X[i].second.second<<")} ";
cerr<<"\n";
}
void Build(int id, int tl, int tr){
if (tr-tl==1){
seg[id]=F[X[tl]][X[tr]];
return ;
}
int mid=(tl+tr)>>1;
Build(id<<1, tl, mid);
Build(id<<1 | 1, mid, tr);
seg[id]=Merge(seg[id<<1], seg[id<<1 | 1]);
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>n>>m>>T>>L;
m<<=1;
assert(T==1); // 62 points
for (int i=0; i<m; ){
cin>>u>>v>>x;
U[i]=u, V[i]=v, W[i]=x, G[u].pb(i++);
U[i]=v, V[i]=u, W[i]=x, G[v].pb(i++);
}
memset(dist, 63, sizeof(dist));
for (int i=0; i<m; i++){
pq.push({dist[i][i]=0, i});
while (pq.size()){
int x=pq.top().second;
pq.pop();
if (mark[i][x]) continue ;
mark[i][x]=1;
for (int y:G[V[x]]) if (x^y^1 && dist[i][y]>dist[i][x]+W[y])
pq.push({dist[i][y]=dist[i][x]+W[y], y});
}
}
for (int i=0; i<5; i++) F[0][0][i]={INF, {-1, -1}};
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) F[i][j]=F[0][0];
for (int u=1; u<=n; u++) for (int v=u+1; v<=n; v++){
for (int i:G[u]) for (int j:G[v]) F[u][v][0]=min(F[u][v][0], {W[i]+dist[i][j^1], {i>>1, j>>1}});
int a=F[u][v][0].second.first, b=F[u][v][0].second.second;
for (int i:G[u]) for (int j:G[v]){
if ((i>>1)!=a) F[u][v][1]=min(F[u][v][1], {W[i]+dist[i][j^1], {i>>1, j>>1}});
if ((j>>1)!=b) F[u][v][2]=min(F[u][v][2], {W[i]+dist[i][j^1], {i>>1, j>>1}});
}
int c=F[u][v][1].second.first, d=F[u][v][1].second.second;
int e=F[u][v][2].second.first, f=F[u][v][2].second.second;
for (int i:G[u]) for (int j:G[v]){
if ((i>>1)!=a && (j>>1)!=d) F[u][v][3]=min(F[u][v][3], {W[i]+dist[i][j^1], {i>>1, j>>1}});
if ((i>>1)!=e && (j>>1)!=b) F[u][v][4]=min(F[u][v][4], {W[i]+dist[i][j^1], {i>>1, j>>1}});
}
for (int i=0; i<5; i++) F[v][u][i]={F[u][v][i].first, {F[u][v][i].second.second, F[u][v][i].second.first}};
}
// cerr<<"F[1][2]: ";print(F[1][2]);
// cerr<<"F[1][3]: ";print(F[1][3]);
// cerr<<"F[2][3]: ";print(F[2][3]);
for (int i=1; i<=L; i++) cin>>X[i];
while (T--){
cin>>x>>y;
X[x]=y;
Build(1, 1, n);
ll res=seg[1][0].first;
if (res>=INF) res=-1;
cout<<res<<"\n";
}
return 0;
}
/*
3 3 1 3
1 2 1
2 3 1
1 3 1
1
2
3
3 1
*/
Compilation message
wild_boar.cpp: In function 'DATA Merge(DATA, DATA)':
wild_boar.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i=1; i<vec.size() && sz<5; i++){
| ~^~~~~~~~~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:113:7: warning: unused variable 'c' [-Wunused-variable]
113 | int c=F[u][v][1].second.first, d=F[u][v][1].second.second;
| ^
wild_boar.cpp:114:34: warning: unused variable 'f' [-Wunused-variable]
114 | int e=F[u][v][2].second.first, f=F[u][v][2].second.second;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
126060 KB |
Output is correct |
| 2 |
Incorrect |
66 ms |
126060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
126060 KB |
Output is correct |
| 2 |
Incorrect |
66 ms |
126060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
126060 KB |
Output is correct |
| 2 |
Incorrect |
66 ms |
126060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
126060 KB |
Output is correct |
| 2 |
Incorrect |
66 ms |
126060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
