#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 dp[2][5];
ll D[2111][2111][5];
vector<pair<int,int> > paths[2111][2111];
vector<ll> W;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
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);
}
/*
int orim = m;
for(int i=0;i<n;i++)
{
adj[n].pb(mp(mp(i,0),m++)); edges.pb({n,i}); W.pb(0);
}
*/
int orim = m; 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();
//cerr<<"DIST : "<<s<<' '<<u<<' '<<d<<'\n';
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(edges[id][0]!=v) vid++;
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; //D[j][i][0] = mn;
paths[i][j].pb(cur); //paths[j][i].pb(cur);
mn = INF; cur = mp(-1,-1);
for(int k:out[i])
{
for(int l:in[j])
{
//cerr<<"OUT "<<i<<' '<<j<<' '<<k<<' '<<l<<'\n';
if(edges[k].se!=paths[i][j][0].fi&&dist[k][l]+W[k]+W[l]<mn)
{
//cerr<<"OUT 2 : "<<i<<' '<<j<<' '<<k<<' '<<l<<'\n';
mn=dist[k][l]+W[k]+W[l];
cur=mp(edges[k].se, edges[l].fi);
}
}
}
D[i][j][1] = mn; //= D[j][i][1] = mn;
paths[i][j].pb(cur); //paths[j][i].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);
}
}
}
D[i][j][2] = mn; //D[j][i][2] = mn;
paths[i][j].pb(cur); //paths[j][i].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);
}
}
}
D[i][j][3] = mn; // D[j][i][3] = mn;
paths[i][j].pb(cur); //paths[j][i].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);
}
}
}
D[i][j][4] = mn; //D[j][i][2] = mn;
paths[i][j].pb(cur); //paths[j][i].pb(cur);
}
}
for(int i=0;i<L;i++)
{
cin>>a[i]; a[i]--;
}
for(int zz=0;zz<q;zz++)
{
int y,z; cin>>y>>z; y--; z--; a[y]=z;
/*
for(int i=0;i<m*2;i++)
{
dp[0][i] = INF;
}
for(int i=0;i<m;i++)
{
for(int j=0;j<2;j++)
{
if(edges[i][j]==a[0])
{
dp[0][getid(i,j)] = 0;
}
}
}
*/
/*
dp[0][getid(orim + a[0],1)] = 0;
for(int i=0;i+1<L;i++)
{
int pre = i&1; int cur = pre^1;
for(int j=0;j<m*2;j++)
{
dp[cur][j] = INF;
}
for(int j=0;j<m*2;j++)
{
if(dp[pre][j]<INF)
{
ll v=dp[pre][j];
for(int k:belong[a[i+1]])
{
if(dist[j][k]<INF)
{
dp[cur][k] = min(dp[cur][k], v + dist[j][k]);
}
}
}
}
}
ll mn = INF;
for(int i=0;i<m*2;i++)
{
mn = min(mn, dp[(L+1)&1][i]);
}
cout<<mn<<'\n';
*/
for(int i=0;i<5;i++) dp[1][i] = D[a[0]][a[1]][i];
for(int i=1;i+1<L;i++)
{
int pre = i&1; int cur = pre^1;
for(int j=0;j<5;j++)
{
dp[cur][j]=INF;
}
for(int j=0;j<5;j++)
{
if(dp[pre][j]<INF)
{
ll v=dp[pre][j];
for(int k=0;k<5;k++)
{
//cerr<<i<<' '<<j<<' '<<k<<' '<<paths[a[i-1]][a[i]][j].fi<<' '<<paths[a[i-1]][a[i]][j].se<<' '<<paths[a[i]][a[i+1]][k].fi<<' '<<paths[a[i]][a[i+1]][k].se<<' '<<D[a[i-1]][a[i]][j]<<' '<<D[a[i]][a[i+1]][k]<<'\n';
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)
{
dp[cur][k] = min(dp[cur][k], v + D[a[i]][a[i+1]][k]);
}
}
}
}
/*
for(int j=0;j<5;j++)
{
cerr<<i<<' '<<j<<' '<<paths[a[i]][a[i+1]][j].fi<<' '<<paths[a[i]][a[i+1]][j].se<<' '<<dp[cur][j]<<'\n';
}
*/
}
ll mn = INF;
for(int i=0;i<5;i++) mn=min(mn,dp[(L+1)&1][i]);
if(mn>=INF) mn=-1;
cout<<mn<<'\n';
}
}
Compilation message
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:74:9: warning: unused variable 'v' [-Wunused-variable]
int v = k.fi.fi; ll w = k.fi.se; int id = k.se;
^
wild_boar.cpp:76:32: warning: unused variable 'v1' [-Wunused-variable]
int u1 = edges[id].fi; int v1 = edges[id].se;
^~
wild_boar.cpp:59:6: warning: unused variable 'orim' [-Wunused-variable]
int orim = m; m*=2;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
105208 KB |
Output is correct |
| 2 |
Incorrect |
92 ms |
105352 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
105208 KB |
Output is correct |
| 2 |
Incorrect |
92 ms |
105352 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
105208 KB |
Output is correct |
| 2 |
Incorrect |
92 ms |
105352 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
105208 KB |
Output is correct |
| 2 |
Incorrect |
92 ms |
105352 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
