제출 #512320

#제출 시각아이디문제언어결과실행 시간메모리
512320MurotYValley (BOI19_valley)C++14
0 / 100
3057 ms37788 KiB
#include<bits/stdc++.h> #define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ll long long #define ff first #define ss second using namespace std; const int N=1e6+7; vector <pair <ll,ll>> g[N]; ll a[N], b[N]; bool u[N]; void dfs(ll v, ll p, ll l){ u[v]=1; for (auto it:g[v]){ if (it.ff != p && it.ss != l){ dfs(it.ff, v, l); } } return ; } int main() { ll n, s, q, e; cin >> n >> s >> q >> e; for (int i=1;i<n;i++){ int x, y; cin >> x >> y >> a[i]; g[x].push_back({y, i}); g[y].push_back({x, i}); } map <ll,ll> mp; for (int i=1;i<=s;i++) cin >> b[i], mp[b[i]]++; while (q--){ int l, r; cin >> l >> r; dfs(r, 0, l); if (u[r] == u[e] and u[r]){ cout <<"escaped\n"; fill(u, u+n+1, 0); } else { queue <ll> q; vector <ll> dc(n+1, 1e9); dc[r]=0; q.push(r); while (!q.empty()){ int x=q.front(); q.pop(); for (auto l:g[x]){ if (dc[l.ff] >= dc[x]+a[l.ss]){ dc[l.ff]=dc[x]+a[l.ss]; q.push(l.ff); } } } ll ans=1e9; for (int i=1;i<=n;i++){ if (mp[i] and u[r] == u[i] and u[r] and i != r) ans=min(ans, dc[i]); } if (ans == 1e9) cout << "oo\n"; else cout << ans <<"\n"; fill(u, u+n+1, 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...