#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define i3 tuple<int,int,int>
#define i4 tuple<int,int,int,int>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,m,l,q;
struct E{ int to,w,id; };
vector<E> al[2005];
vector<ii> w[2005]; //ok so we store the best 2 guys...
priority_queue<i4,vector<i4>,greater<i4> > pq;
void add(int i,ii val){
if (w[i][0]==val || w[i][1]==val) return; //prevent from inserting dupes
if (val.fi<w[i][0].fi){
swap(w[i][0],w[i][1]);
w[i][0]=val;
pq.push({w[i][0].fi,w[i][0].se,i,0});
pq.push({w[i][1].fi,w[i][1].se,i,1});
}
else if (val.fi<w[i][1].fi && w[i][0].se!=val.se){
w[i][1]=val;
pq.push({w[i][1].fi,w[i][1].se,i,1});
}
}
struct dat{
vector<i3> res;
dat(){};
dat (vector<i3> temp){ //pick best 4
map<int,int> m1,m2;
set<ii> s;
sort(all(temp));
for (auto [w,a,b]:temp){
if (m1[a]==2 || m2[b]==2 || s.count({a,b})) continue;
m1[a]++,m2[b]++;
s.insert({a,b});
res.pub({w,a,b});
if (sz(res)==100) break;
}
}
};
dat merge(dat i,dat j){
vector<i3> temp;
for (auto [w,id1,id2]:i.res) for (auto [w2,id3,id4]:j.res){
if (id2!=id3) temp.pub({w+w2,id1,id4});
}
return dat(temp);
}
vector<i3> v[2005];
dat trans[2005][2005];
int arr[100005];
signed main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
cin>>n>>m>>q>>l;
int a,b,c;
rep(x,0,m){
cin>>a>>b>>c;
al[a].pub({b,c,x});
al[b].pub({a,c,x});
}
rep(x,1,n+1){
rep(y,1,n+1) v[y].clear();
for (auto [y,_W,id]:al[x]){
rep(x,1,n+1){
w[x].clear();
rep(y,0,2) w[x].pub({1e18,-1});
}
add(y,{_W,id});
while (!pq.empty()){
int W,id,u,pos;
tie(W,id,u,pos)=pq.top(),pq.pop();
if (w[u][pos]!=ii(W,id)) continue;
for (auto [it,w2,id2]:al[u]) if (id!=id2){
add(it,{W+w2,id2});
}
}
rep(y,1,n+1) for (auto [w,id2]:w[y]){
v[y].pub({w,id,id2});
}
}
rep(y,1,n+1) trans[x][y]=dat(v[y]);
}
rep(x,1,l+1) cin>>arr[x];
while (q--){
cin>>a>>b;
arr[a]=b;
//rep(x,1,l+1) cout<<arr[x]<<" "; cout<<endl;
dat ans=trans[arr[1]][arr[2]];
rep(x,2,l){
ans=merge(ans,trans[arr[x]][arr[x+1]]);
//cout<<x<<":"<<endl;
//for (auto [w,id,id2]:ans.res) cout<<w<<" "<<id<<" "<<id2<<endl;
}
if (ans.res.empty()) cout<<"-1"<<endl;
else cout<<get<0>(ans.res[0])<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
94796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
94796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
94796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
94796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
