#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll p[21][100000],mi[21][100000];
ll ans=1000000000;
int get(int x,int y)
{
if(y<0)
return 0;
int u=1;
int k=0;
//cout<<x<<' ';
while(k<=20&&y>0)
{
if((u&y)==u)
{
ans=min(ans,mi[k][x]);
x=p[k][x];
// cout<<x<<' ';
// cout<<mi[k][x]<<endl;
}
u*=2;
k++;
}
// cout<<endl;
return x;
}
vector<ll>v[100000];
vector<ll>w[100000];
ll m[100000];
ll val[100000];
ll dist[100000];
ll u[100000];
void dfs(int in,int pa)
{
val[in]=1e18;
for(int i=0;i<v[in].size();i++)
{
if(v[in][i]==pa)
{
continue ;
}
p[0][v[in][i]]=in;
dist[v[in][i]]=dist[in]+w[in][i];
u[v[in][i]]=u[in]+1;
dfs(v[in][i],in);
val[in]=min(val[in],val[v[in][i]]+w[in][i]);
}
if(m[in]==1)
val[in]=0;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("balancing.in","r",stdin);
// freopen("balancing.out","w",stdout);
ll n,s,q,e;
cin>>n>>s>>q>>e;
ll a[n],b[n],c[n];
e--;
for(int i=0;i<n-1;i++)
{
cin>>a[i]>>b[i]>>c[i];
a[i]--;
b[i]--;
v[a[i]].push_back(b[i]);
w[a[i]].push_back(c[i]);
v[b[i]].push_back(a[i]);
w[b[i]].push_back(c[i]);
}
for(int i=0;i<s;i++)
{
int z;
cin>>z;
z--;
m[z]=1;
}
dfs(e,e);
p[0][e]=e;
for(int i=0;i<n;i++)
{
val[i]-=dist[i];
mi[0][i]=val[i];
//cout<<dist[i]<<' ';
}
//cout<<endl;
for(int i=1;i<20;i++)
{
for(int y=0;y<n;y++)
{
p[i][y]=p[i-1][p[i-1][y]];
mi[i][y]=min(mi[i-1][y],mi[i-1][p[i-1][y]]);
/*if(i<4)
{
cout<<mi[i][y]<<' ';
}*/
/* if(i==1)
cout<<p[0][y]<<' ';*/
}
/*if(i<4)
cout<<endl;*/
}
while(q--)
{
int x,y;
cin>>x>>y;
swap(x,y);
// cout<<111<<endl;
y--;
x--;
int st,en;
st=b[y];
en=a[y];
if(dist[a[y]]<dist[b[y]])
{
st=a[y];
en=b[y];
}
//cout<<222<<endl;
ll di=u[x]-u[en];
ans=1000000000000000000;
int c=get(x,di);
//cout<<c<<endl;
//cout<<333<<endl;
//cout<<ans<<' ';
if(c!=en||di<0)
{
cout<<"escaped"<<endl;
continue;
}
ans=1000000000000000000;
get(x,di+1);
//cout<<ans<<' ';
if(min(val[x]+dist[x],dist[x]+ans)<100000000000000000)
cout<<min(val[x]+dist[x],dist[x]+ans)<<endl;
else
cout<<"oo"<<endl;
}
}
Compilation message
valley.cpp: In function 'void dfs(int, int)':
valley.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=0;i<v[in].size();i++)
| ~^~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:124:9: warning: variable 'st' set but not used [-Wunused-but-set-variable]
124 | int st,en;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
5332 KB |
Output is correct |
2 |
Correct |
16 ms |
5428 KB |
Output is correct |
3 |
Correct |
18 ms |
5424 KB |
Output is correct |
4 |
Correct |
17 ms |
5404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
5332 KB |
Output is correct |
2 |
Correct |
16 ms |
5428 KB |
Output is correct |
3 |
Correct |
18 ms |
5424 KB |
Output is correct |
4 |
Correct |
17 ms |
5404 KB |
Output is correct |
5 |
Correct |
5 ms |
5692 KB |
Output is correct |
6 |
Correct |
5 ms |
5716 KB |
Output is correct |
7 |
Correct |
6 ms |
5640 KB |
Output is correct |
8 |
Correct |
5 ms |
5636 KB |
Output is correct |
9 |
Correct |
6 ms |
5684 KB |
Output is correct |
10 |
Correct |
5 ms |
5640 KB |
Output is correct |
11 |
Correct |
6 ms |
5688 KB |
Output is correct |
12 |
Correct |
5 ms |
5716 KB |
Output is correct |
13 |
Correct |
6 ms |
5716 KB |
Output is correct |
14 |
Correct |
6 ms |
5716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
288 ms |
50392 KB |
Output is correct |
2 |
Correct |
278 ms |
49672 KB |
Output is correct |
3 |
Correct |
283 ms |
53472 KB |
Output is correct |
4 |
Correct |
339 ms |
55124 KB |
Output is correct |
5 |
Correct |
313 ms |
55288 KB |
Output is correct |
6 |
Correct |
429 ms |
56808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
5332 KB |
Output is correct |
2 |
Correct |
16 ms |
5428 KB |
Output is correct |
3 |
Correct |
18 ms |
5424 KB |
Output is correct |
4 |
Correct |
17 ms |
5404 KB |
Output is correct |
5 |
Correct |
5 ms |
5692 KB |
Output is correct |
6 |
Correct |
5 ms |
5716 KB |
Output is correct |
7 |
Correct |
6 ms |
5640 KB |
Output is correct |
8 |
Correct |
5 ms |
5636 KB |
Output is correct |
9 |
Correct |
6 ms |
5684 KB |
Output is correct |
10 |
Correct |
5 ms |
5640 KB |
Output is correct |
11 |
Correct |
6 ms |
5688 KB |
Output is correct |
12 |
Correct |
5 ms |
5716 KB |
Output is correct |
13 |
Correct |
6 ms |
5716 KB |
Output is correct |
14 |
Correct |
6 ms |
5716 KB |
Output is correct |
15 |
Correct |
288 ms |
50392 KB |
Output is correct |
16 |
Correct |
278 ms |
49672 KB |
Output is correct |
17 |
Correct |
283 ms |
53472 KB |
Output is correct |
18 |
Correct |
339 ms |
55124 KB |
Output is correct |
19 |
Correct |
313 ms |
55288 KB |
Output is correct |
20 |
Correct |
429 ms |
56808 KB |
Output is correct |
21 |
Correct |
279 ms |
53040 KB |
Output is correct |
22 |
Correct |
283 ms |
52296 KB |
Output is correct |
23 |
Correct |
298 ms |
52268 KB |
Output is correct |
24 |
Correct |
359 ms |
54184 KB |
Output is correct |
25 |
Correct |
389 ms |
56844 KB |
Output is correct |
26 |
Correct |
251 ms |
53324 KB |
Output is correct |
27 |
Correct |
276 ms |
52612 KB |
Output is correct |
28 |
Correct |
285 ms |
52388 KB |
Output is correct |
29 |
Correct |
327 ms |
53992 KB |
Output is correct |
30 |
Correct |
379 ms |
55136 KB |
Output is correct |
31 |
Correct |
243 ms |
53844 KB |
Output is correct |
32 |
Correct |
274 ms |
53160 KB |
Output is correct |
33 |
Correct |
268 ms |
53068 KB |
Output is correct |
34 |
Correct |
330 ms |
54988 KB |
Output is correct |
35 |
Correct |
357 ms |
57392 KB |
Output is correct |
36 |
Correct |
344 ms |
55356 KB |
Output is correct |