Submission #915569

#TimeUsernameProblemLanguageResultExecution timeMemory
915569AndrijaMValley (BOI19_valley)C++14
36 / 100
166 ms14248 KiB
#include <bits/stdc++.h> using namespace std; const long long maxn=1e5+10; const long long logn=25; const long long mod=1e9+7; long long n,s,q,e; vector<pair<long long,long long>>g[maxn]; set<long long>ins; vector<pair<long long,long long>>pr; struct node { long long idx; long long dis; node(){} node(long long _idx,long long _dis) { idx=_idx; dis=_dis; } bool operator <(const node &tmp)const { return dis>tmp.dis; } }; int main() { cin>>n>>s>>q>>e; e--; for(long long i=0;i<n-1;i++) { long long a,b,c; cin>>a>>b>>c; a--;b--; g[a].push_back({b,c}); g[b].push_back({a,c}); pr.push_back({a,b}); } for(long long i=0;i<s;i++) { long long pom; cin>>pom; ins.insert(pom-1); } while(q--) { long long idxe,st; cin>>idxe>>st; idxe--; st--; long long n1=pr[idxe].first; long long n2=pr[idxe].second; ///cout<<n1<<" "<<n2<<endl; if(n<1100) { ///kolku e odalecen od S priority_queue<node>Q; Q.push(node(st,0)); long long d[n]; for(long long pi=0;pi<n;pi++) { d[pi]=1e18; } d[st]=0; bool ok=false; while(!Q.empty()) { node teme=Q.top();Q.pop(); if(teme.idx==e) { cout<<"escaped"<<endl; ok=true; break; } for(auto ax:g[teme.idx]) { if((teme.idx==n1 && ax.first==n2) || (teme.idx==n2 && ax.first==n1)) { continue; } if(teme.dis+ax.second<d[ax.first]) { d[ax.first]=teme.dis+ax.second; Q.push(node(ax.first,d[ax.first])); } } } long long ans=1e18; for(auto pom:ins) { ans=min(ans, d[pom]); } if(!ok) { if(ans!=1e18) cout<<ans<<endl; else { cout<<"oo"<<endl; } } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...