| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 168524 | achibasadzishvili | Evacuation plan (IZhO18_plan) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
nclude <bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
ll k,n,m,qq,d[100005],p[100005],c[100005],ans[100005],las,fix[100005];
ll qu[100005],sz[100005];
vector<ll>vec[100005];
vector<pair<ll,ll> >v[100005],q[100005];
set<pair<ll,ll> >st;
ll find(ll x){
if(p[x] == x)return x;
return p[x] = find(p[x]);
}
void join(ll x,ll y){
x = find(x);
y = find(y);
if(x == y)return;
if(sz[x] < sz[y])swap(x , y);
qu[x] += qu[y];
sz[x] += sz[y];
for(int i=0; i<q[y].size(); i++){
if(find(q[y][i].f) == x)
ans[q[y][i].s] = min(ans[q[y][i].s] , las);
q[x].pb(q[y][i]);
}
for(int i=0; i<vec[y].size(); i++){
vec[x].pb(vec[y][i]);
}
p[y] = x;
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=1; i<=m; i++){
int x,y,z;
cin >> x >> y >> z;
v[x].pb(mp(y , z));
v[y].pb(mp(x , z));
}
cin >> k;
for(int i=1; i<=n; i++){
d[i] = 1000000000;
}
for(int i=1; i<=k; i++){
cin >> c[i];
st.insert(mp(0LL , c[i]));
d[c[i]] = 0;
}
while(st.size()){
ll x = (*st.begin()).s;
st.erase(st.begin());
for(int i=0; i<v[x].size(); i++){
ll to = v[x][i].f;
if(d[to] > d[x] + v[x][i].s){
if(st.find(mp(d[to] , to)) != st.end())st.erase(st.find(mp(d[to] , to)));
d[to] = d[x] + v[x][i].s;
st.insert(mp(d[to] , to));
}
}
}
cin >> qq;
for(int i=1; i<=qq; i++){
ans[i] = 1000000000;
int x,y;
cin >> x >> y;
q[x].pb(mp(y , i));
q[y].pb(mp(x , i));
}
vector<pair<ll,ll> >g;
for(int i=1; i<=n; i++){
g.pb(mp(d[i] , i));
}
sort(g.begin() , g.end());
reverse(g.begin() , g.end());
for(int i=1; i<=n; i++){
p[i] = i;
qu[i] = (int)q[i].size();
vec[i].pb(i);
sz[i] = 1;
}
for(int i=0; i<g.size(); i++){
las = g[i].f;
fix[g[i].s] = 1;
for(int j=0; j<v[g[i].s].size(); j++){
ll to = v[g[i].s][j].f;
if(fix[to] == 1){
join(g[i].s , to);
}
}
}
for(int i=1; i<=qq; i++)
cout << ans[i] << '\n';
return 0;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/