This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9;
const ll inf = 2e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi = 3.14159265359;
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 4003;
const ll A = 911382323;
const ll B = 972663749;
int n, m, t, len;
int a[200000];
vector<int> g[mxn];
int l[mxn], r[mxn], w[mxn];
ll dist[2][mxn][2][mxn];
bool vis[2][mxn][2][mxn];
void dijkstra(int edge, int side){
pq<pair<ll, pii> > Q;
Q.push({0, {edge, side}});
dist[side][edge][side][edge] = 0;
while(!Q.empty()){
int e = Q.top().nd.st;
int s = Q.top().nd.nd;
Q.pop();
if(vis[side][edge][s][e]) continue;
vis[side][edge][s][e] = true;
int node = l[e];
if(s == 1) node = r[e];
for(auto edge2 : g[node]){
if(edge2 == e || edge2>=m) continue;
int side2 = 0;
if(l[edge2] == node) side2 = 1;
if(dist[side][edge][s][e] + w[edge2] < dist[side][edge][side2][edge2]){
dist[side][edge][side2][edge2] = dist[side][edge][s][e] + w[edge2];
Q.push({-dist[side][edge][side2][edge2], {edge2, side2}});
}
}
}
}
void prec(){
fr(i, 0, 2) fr(j, 0, n+m) fr(k, 0, 2)fr(p, 0, n+m) dist[i][j][k][p] = inf;
fr(i, 0, n){
for(auto edge : g[i]){
int side = 0;
if(r[edge] == i) side = 1;
dijkstra(edge, side);
}
}
}
void solve(){
cin >> n >> m >> t >> len;
fr(i, 0, m){
cin >> l[i] >> r[i] >> w[i];
--l[i], --r[i];
g[l[i]].pb(i);
g[r[i]].pb(i);
}
fr(i, 0, n){
l[i+m] = r[i+m] = i;
g[i].pb(i+m);
}
fr(i, 0, len){
cin >> a[i];
--a[i];
}
prec();
fr(I, 0, t){
int p, q;
cin >> p >> q;
a[p-1] = q-1;
pq<pair<ll, pii> > Q;
Q.push({0, {a[0]+m, 1}});
fr(i, 1, len){
vector<pair<ll,pii> > v;
while(!Q.empty()){
ll w = Q.top().st;
int side = Q.top().nd.nd;
int edge = Q.top().nd.st;
Q.pop();
for(auto e : g[a[i]]){
if(e >= m) continue;
int s = 0;
if(a[i] == r[e]) s = 1;
v.pb({min(inf, w + dist[side][edge][s][e]), {e, s}});
}
}
sort(all(v));
fr(i, 0, (int)v.size()){
if(v[i].st == inf) continue;
Q.push({v[i].st,{v[i].nd.st, v[i].nd.nd}});
int ed = v[i].nd.st;
while(i + 1 < (int)v.size() && v[i+1].nd.st == ed) i ++;
}
if(v.empty()){
Q.push({inf,{0, 0}});
break;
}
while(Q.size()>2){
Q.pop();
}
}
while(Q.size()>1) Q.pop();
ll ans = Q.top().st;
if(ans >= inf) ans = -1;
cout<<ans<<endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tc = 1;
//cin >> tc;
while(tc--) solve();
}
/*
5 10 1 10
1 2 8
1 3 5
1 4 2
1 5 1
2 3 7
2 4 9
2 5 6
3 4 10
3 5 10
4 5 6
4
2
4
3
5
3
1
4
3
5
3 5
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |