#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int,int>
#define pli pair<ll,pair<pi,int>>
#define x first
#define y second
int n,m,t,l;
vector<ll> func(int N, int M, int T, int L, vector<int> A, vector<int> B, vector<int> C, vector<int> X, vector<int> P, vector<int> Q){
n=N;m=M;t=T;l=L;
vector<vector<pi>> g(n);
for(int i=0;i<m;i++){
--A[i];--B[i];
g[A[i]].push_back({B[i],C[i]});
g[B[i]].push_back({A[i],C[i]});
}
vector<vector<ll>> dist(n,vector<ll>(n,1e18)),dist1(n,vector<ll>(n,1e18));//reg dist, dist without the same start
vector<vector<ll>> nxt(n,vector<ll>(n,-1)),nxt1(n,vector<ll>(n,-1));
vector<vector<ll>> lst(n,vector<ll>(n,-1)),lst1(n,vector<ll>(n,-1));
vector<vector<ll>> dist2(n,vector<ll>(n,1e18)),dist3(n,vector<ll>(n,1e18));//not the same end, not the same both
vector<vector<ll>> nxt2(n,vector<ll>(n,-1)),nxt3(n,vector<ll>(n,-1));
vector<vector<ll>> lst2(n,vector<ll>(n,-1)),lst3(n,vector<ll>(n,-1));
for(int i=0;i<n;i++){
dist[i][i] = 0;
multiset<pli> st;
for(int j=0;j<n;j++) st.insert({dist[i][j],{{j,-1},-1}});
for(int j=0;j<n;j++) st.insert({dist1[i][j],{{j,-1},-1}});
for(int j=0;j<n;j++) st.insert({dist2[i][j],{{j,-1},-1}});
for(int j=0;j<n;j++) st.insert({dist3[i][j],{{j,-1},-1}});
while(st.size()){
pli pr = *st.begin(); st.erase(st.begin());
for(pi &p : g[pr.y.x.x]){
if(dist[i][p.x] > pr.x+p.y && pr.y.y!=p.x){
if(nxt[i][p.x] != pr.y.x.x){
st.erase(st.find({dist1[i][p.x],{{p.x,lst1[i][p.x]},nxt1[i][p.x]}}));
dist1[i][p.x] = dist[i][p.x];
nxt1[i][p.x]=nxt[i][p.x];
lst1[i][p.x]=lst[i][p.x];
st.insert({dist1[i][p.x],{{p.x,lst1[i][p.x]},nxt1[i][p.x]}});
}
if(lst[i][p.x] != (pr.y.x.x==i ? p.x : pr.y.x.y)){
st.erase(st.find({dist2[i][p.x],{{p.x,lst2[i][p.x]},nxt2[i][p.x]}}));
dist2[i][p.x] = dist[i][p.x];
nxt2[i][p.x]=nxt[i][p.x];
lst2[i][p.x]=lst[i][p.x];
st.insert({dist2[i][p.x],{{p.x,lst2[i][p.x]},nxt2[i][p.x]}});
}
if(lst[i][p.x] != (pr.y.x.x==i ? p.x : pr.y.x.y) && nxt[i][p.x] != pr.y.x.x){
st.erase(st.find({dist3[i][p.x],{{p.x,lst3[i][p.x]},nxt3[i][p.x]}}));
dist3[i][p.x] = dist[i][p.x];
nxt3[i][p.x]=nxt[i][p.x];
lst3[i][p.x]=lst[i][p.x];
st.insert({dist3[i][p.x],{{p.x,lst3[i][p.x]},nxt3[i][p.x]}});
}
st.erase(st.find({dist[i][p.x],{{p.x,lst[i][p.x]},nxt[i][p.x]}}));
dist[i][p.x] = pr.x+p.y;
nxt[i][p.x]=pr.y.x.x;
lst[i][p.x]= (pr.y.x.x==i) ? p.x : pr.y.x.y;
st.insert({dist[i][p.x],{{p.x,lst[i][p.x]},nxt[i][p.x]}});
}
if(dist1[i][p.x] > pr.x + p.y && nxt[i][p.x] != pr.y.x.x && pr.y.y != p.x){
st.erase(st.find({dist1[i][p.x],{{p.x,lst1[i][p.x]},nxt1[i][p.x]}}));
dist1[i][p.x] = pr.x+p.y;
nxt1[i][p.x]=pr.y.x.x;
lst1[i][p.x] = pr.y.x.x==i ? p.x : pr.y.x.y;
st.insert({dist1[i][p.x],{{p.x,lst1[i][p.x]},nxt1[i][p.x]}});
}
if(dist2[i][p.x] > pr.x + p.y && (lst[i][p.x] != (pr.y.x.x==i ? p.x : pr.y.x.y)) && pr.y.y != p.x){
st.erase(st.find({dist2[i][p.x],{{p.x,lst2[i][p.x]},nxt2[i][p.x]}}));
dist2[i][p.x] = pr.x+p.y;
nxt2[i][p.x]=pr.y.x.x;
lst2[i][p.x] = pr.y.x.x==i ? p.x : pr.y.x.y;
st.insert({dist2[i][p.x],{{p.x,lst2[i][p.x]},nxt2[i][p.x]}});
}
if(dist3[i][p.x] > pr.x + p.y && (lst[i][p.x] != (pr.y.x.x==i ? p.x : pr.y.x.y)) && nxt[i][p.x] != pr.y.x.x && pr.y.y != p.x){
st.erase(st.find({dist3[i][p.x],{{p.x,lst3[i][p.x]},nxt3[i][p.x]}}));
dist3[i][p.x] = pr.x+p.y;
nxt3[i][p.x]=pr.y.x.x;
lst3[i][p.x] = pr.y.x.x==i ? p.x : pr.y.x.y;
st.insert({dist3[i][p.x],{{p.x,lst3[i][p.x]},nxt3[i][p.x]}});
}
}
}
}
/*for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<i<<' '<<j<<endl;
cout<<dist[i][j]<<' '<<nxt[i][j]<<' '<<lst[i][j]<<endl;
cout<<dist1[i][j]<<' '<<nxt1[i][j]<<' '<<lst1[i][j]<<endl;
cout<<dist2[i][j]<<' '<<nxt2[i][j]<<' '<<lst2[i][j]<<endl;
cout<<dist3[i][j]<<' '<<nxt3[i][j]<<' '<<lst3[i][j]<<endl;
}
}*/
vector<ll> res(t,-1);
for(int i=0;i<l;i++) X[i]--;
for(int i=0;i<t;i++){
X[P[i]-1]=Q[i]-1;
int lb = -1, ls = -1;
ll rb = 0, rs = 0;
for(int j=1;j<l;j++){
vector<int> l; vector<ll> r;
if(lb != nxt[X[j]][X[j-1]]){ r.push_back(rb+dist[X[j]][X[j-1]]); l.push_back(lst[X[j]][X[j-1]]); }
if(lb != nxt1[X[j]][X[j-1]]){ r.push_back(rb+dist1[X[j]][X[j-1]]); l.push_back(lst1[X[j]][X[j-1]]); }
if(lb != nxt2[X[j]][X[j-1]]){ r.push_back(rb+dist2[X[j]][X[j-1]]); l.push_back(lst2[X[j]][X[j-1]]); }
if(lb != nxt3[X[j]][X[j-1]]){ r.push_back(rb+dist3[X[j]][X[j-1]]); l.push_back(lst3[X[j]][X[j-1]]); }
if(rs<1e18 && ls != nxt[X[j]][X[j-1]]){ r.push_back(rs+dist[X[j]][X[j-1]]); l.push_back(lst[X[j]][X[j-1]]); }
if(rs<1e18 && ls != nxt1[X[j]][X[j-1]]){ r.push_back(rs+dist1[X[j]][X[j-1]]); l.push_back(lst1[X[j]][X[j-1]]); }
if(rs<1e18 && ls != nxt2[X[j]][X[j-1]]){ r.push_back(rs+dist2[X[j]][X[j-1]]); l.push_back(lst2[X[j]][X[j-1]]); }
if(rs<1e18 && ls != nxt3[X[j]][X[j-1]]){ r.push_back(rs+dist3[X[j]][X[j-1]]); l.push_back(lst3[X[j]][X[j-1]]); }
rb=rs=1e18; lb=ls=-1;
for(int h=0;h<l.size();h++){
if(r[h] < rb){
rb=r[h];
lb=l[h];
}
}
for(int h=0;h<l.size();h++){
if(r[h] < rs && l[h]!=lb){
rs=r[h];
ls=l[h];
}
}
if(rb == 1e18){
rb=-1;
break;
}
//cout<<rb<<' '<<lb<<endl;
//cout<<rs<<' '<<ls<<endl;
}
res[i]=rb;
}
return res;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int N,M,T,L; cin>>N>>M>>T>>L;
vector<int> A(M),B(M),C(M);
for(int i=0;i<M;i++) cin>>A[i]>>B[i]>>C[i];
vector<int> X(L);
for(int i=0;i<L;i++) cin>>X[i];
vector<int> P(T),Q(T);
for(int i=0;i<T;i++) cin>>P[i]>>Q[i];
vector<ll> res = func(N,M,T,L,A,B,C,X,P,Q);
for(ll i : res) cout<<i<<' '; cout<<endl;
}
Compilation message
wild_boar.cpp: In function 'std::vector<long long int> func(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
wild_boar.cpp:115:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int h=0;h<l.size();h++){
| ~^~~~~~~~~
wild_boar.cpp:121:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int h=0;h<l.size();h++){
| ~^~~~~~~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:150:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
150 | for(ll i : res) cout<<i<<' '; cout<<endl;
| ^~~
wild_boar.cpp:150:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
150 | for(ll i : res) cout<<i<<' '; cout<<endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
448 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
448 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
448 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
448 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
