#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
vector<pair<int,int> > edges;
ll dist[4111][4111];
int n,m,q,L;
vector<pair<ii,int> > adj[2111];
vi in[2111];
vi out[2111];
ll orid[2001][2001];
int getid(int a, int b)
{
return (a*2+b);
}
const ll INF=ll(1e18);
int a[211111];
ll D[2111][2111][5];
vector<pair<int,int> > paths[2111][2111];
vector<ll> W;
const int DIM = 5;
struct state
{
ll a[DIM][DIM];
ll *operator [] (int r) { return a[r]; };
state(ll x = 0)
{
memset(a, 0, sizeof a);
if(x)
{
for(int i = 0; i < DIM; i++)
{
for(int j=0;j < DIM;j++)
{
if(i==j) a[i][j]=0;
else a[i][j] = x;
}
}
}
}
};
state operator + (state A, state B)
{
state C;
for(int i=0;i<DIM;i++)
{
for(int j=0;j<DIM;j++)
{
C[i][j] = INF;
}
for(int j=0;j<DIM;j++)
{
for(int k=0;k<DIM;k++)
{
C[i][k] = min(C[i][k], A[j][k] + B[i][j]);
}
}
}
return C;
}
state st[263000];
void build(int n)
{
for(int i = n - 1; i > 0; --i)
{
st[i] = st[i<<1] + st[i<<1|1];
}
}
void modify(int n, int p, state value)
{
for(st[p += n] = value; p >>= 1; )
{
st[p] = st[p<<1] + st[p<<1|1];
}
}
state construct(int i)
{
state cur;
for(int j=0;j<DIM;j++){for(int k=0;k<DIM;k++){cur[j][k]=INF;}}
for(int j=0;j<DIM;j++)
{
for(int k=0;k<DIM;k++)
{
if(paths[a[i-1]][a[i]][j].se!=-1&&paths[a[i]][a[i+1]][k].fi!=-1&&paths[a[i-1]][a[i]][j].se!=paths[a[i]][a[i+1]][k].fi)
{
cur[k][j] = min(cur[k][j], D[a[i]][a[i+1]][k]);
}
}
}
return cur;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
for(int i=0;i<263000;i++) st[i] = state(INF);
cin>>n>>m>>q>>L;
for(int i=0;i<m;i++)
{
int u,v,w; cin>>u>>v>>w; u--; v--; edges.pb({u,v}); W.pb(w); edges.pb({v,u}); W.pb(w); orid[u][v]=orid[v][u]=w;
adj[u].pb(mp(mp(v,w),i*2)); adj[v].pb(mp(mp(u,w),i*2+1));
out[u].pb(i*2); out[v].pb(i*2+1);
in[u].pb(i*2+1); in[v].pb(i*2);
}
m*=2;
for(int i=0;i<m;i++)
{
priority_queue<ii,vector<ii>,greater<ii> > pq;
int s = i;
pq.push(mp(0,s));
for(int k=0;k<m;k++) dist[s][k] = INF;
dist[s][s] = 0;
while(!pq.empty())
{
ll d=pq.top().fi; int u = pq.top().se; pq.pop();
int vertex = edges[u].se; int edgeno = u;
for(auto k:adj[vertex])
{
int v = k.fi.fi; ll w = k.fi.se; int id = k.se;
if(id/2==edgeno/2) continue;
int u1 = edges[id].fi; int v1 = edges[id].se;
assert(u1==vertex);
if(dist[s][id]>d)
{
dist[s][id] = d;
pq.push(mp(d+w, id));
}
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j) continue;
ll mn=INF; ii cur=mp(-1,-1);
for(int k:out[i])
{
for(int l:in[j])
{
if(dist[k][l]+W[k]+W[l]<mn)
{
mn=dist[k][l]+W[k]+W[l];
cur=mp(edges[k].se, edges[l].fi);
}
}
}
if(orid[i][j]>0)
{
if(orid[i][j]<mn)
{
mn=orid[i][j];
cur=mp(j,i);
}
}
D[i][j][0] = mn;
paths[i][j].pb(cur);
mn = INF; cur = mp(-1,-1);
for(int k:out[i])
{
for(int l:in[j])
{
if(edges[k].se!=paths[i][j][0].fi&&dist[k][l]+W[k]+W[l]<mn)
{
mn=dist[k][l]+W[k]+W[l];
cur=mp(edges[k].se, edges[l].fi);
}
}
}
if(orid[i][j]>0)
{
if(orid[i][j]<mn&&j!=paths[i][j][0].fi)
{
mn=orid[i][j];
cur=mp(j,i);
}
}
D[i][j][1] = mn;
paths[i][j].pb(cur);
mn = INF; cur = mp(-1,-1);
for(int k:out[i])
{
for(int l:in[j])
{
if(edges[k].se!=paths[i][j][0].fi&&edges[l].fi!=paths[i][j][1].se&&dist[k][l]+W[k]+W[l]<mn)
{
mn=dist[k][l]+W[k]+W[l];
cur=mp(edges[k].se, edges[l].fi);
}
}
}
if(orid[i][j]>0)
{
if(orid[i][j]<mn&&j!=paths[i][j][0].fi&&i!=paths[i][j][1].se)
{
mn=orid[i][j];
cur=mp(j,i);
}
}
D[i][j][2] = mn;
paths[i][j].pb(cur);
mn = INF; cur = mp(-1,-1);
for(int k:out[i])
{
for(int l:in[j])
{
if(edges[l].fi!=paths[i][j][0].se&&dist[k][l]+W[k]+W[l]<mn)
{
mn=dist[k][l]+W[k]+W[l];
cur=mp(edges[k].se, edges[l].fi);
}
}
}
if(orid[i][j]>0)
{
if(orid[i][j]<mn&&i!=paths[i][j][0].se)
{
mn=orid[i][j];
cur=mp(j,i);
}
}
D[i][j][3] = mn;
paths[i][j].pb(cur);
mn = INF; cur = mp(-1,-1);
for(int k:out[i])
{
for(int l:in[j])
{
if(edges[k].se!=paths[i][j][3].fi&&edges[l].fi!=paths[i][j][0].se&&dist[k][l]+W[k]+W[l]<mn)
{
mn=dist[k][l]+W[k]+W[l];
cur=mp(edges[k].se, edges[l].fi);
}
}
}
if(orid[i][j]>0)
{
if(orid[i][j]<mn&&j!=paths[i][j][3].fi&&i!=paths[i][j][0].se)
{
mn=orid[i][j];
cur=mp(j,i);
}
}
D[i][j][4] = mn;
paths[i][j].pb(cur);
}
}
for(int i=0;i<L;i++)
{
cin>>a[i]; a[i]--;
}
ll BIGL = 1;
while(BIGL<L-2) BIGL*=2;
for(int i=1;i+1<L;i++)
{
st[BIGL+i-1] = construct(i);
}
build(BIGL);
for(int zz=0;zz<q;zz++)
{
int y,z; cin>>y>>z; y--; z--; a[y]=z;
if(y>=1&&y+1<L)
{
modify(BIGL, y-1, construct(y));
}
if(y>=2&&y<L)
{
modify(BIGL, y-2, construct(y-1));
}
/*
if(y+2<L)
{
modify(BIGL, y, construct(y+1));
}
*/
vector<ll> dp;
for(int i=0;i<5;i++) dp.pb(D[a[0]][a[1]][i]);
ll ans = INF;
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
ans = min(ans, dp[j] + st[1][i][j]);
}
}
if(ans>=INF) ans=-1;
cout<<ans<<'\n';
}
}
Compilation message
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:143:9: warning: unused variable 'v' [-Wunused-variable]
int v = k.fi.fi; ll w = k.fi.se; int id = k.se;
^
wild_boar.cpp:145:32: warning: unused variable 'v1' [-Wunused-variable]
int u1 = edges[id].fi; int v1 = edges[id].se;
^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
132 ms |
156792 KB |
Output is correct |
| 2 |
Correct |
133 ms |
157008 KB |
Output is correct |
| 3 |
Incorrect |
131 ms |
157016 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
132 ms |
156792 KB |
Output is correct |
| 2 |
Correct |
133 ms |
157008 KB |
Output is correct |
| 3 |
Incorrect |
131 ms |
157016 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
132 ms |
156792 KB |
Output is correct |
| 2 |
Correct |
133 ms |
157008 KB |
Output is correct |
| 3 |
Incorrect |
131 ms |
157016 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
132 ms |
156792 KB |
Output is correct |
| 2 |
Correct |
133 ms |
157008 KB |
Output is correct |
| 3 |
Incorrect |
131 ms |
157016 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
