제출 #1307938

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307938		shisp1	Valley (BOI19_valley)	C++20	0 / 100	3094 ms	27768 KiB

valley

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define int long long
using namespace std;
const int mod = 1e9+7;
const ll inf = 1e18;
const int N = 2e5+5;
int n,s,q,e, a[N], u[N], v[N], w[N];
set<pair<int,int>>g[N];
void solve() {
    cin >> n >> s >> q >> e;
    for(int i = 1;i<n;i++) {
        cin >> u[i] >> v[i] >> w[i];
        g[u[i]].insert({v[i],w[i]});
        g[v[i]].insert({u[i],w[i]});
    }
    for(int i = 1;i<=s;i++) {
        cin >> a[i];
    }
    while(q--){
        int i,r;
        cin >> i >> r;
        int uu = u[i], vv = v[i], ww = w[i];
        g[uu].erase({vv,ww});
        g[vv].erase({uu,ww});
        vector<int>dist(n+1,inf);
        dist[r] = 0;
        set<pair<int,int>>st;
        st.insert({0,r});
        while(st.size()) {
            auto [dv,ver] = *st.begin();
            st.erase(st.begin());
            for(auto [to,weight]:g[ver]) {
                if(dist[to]>dist[ver]+weight) {
                    st.erase({dist[to],to});
                    dist[to] = dist[ver]+weight;
                    st.insert({dist[to],to});
                }
            }
        }
        if(dist[e]!=inf) {
            cout << "escaped\n";
            continue;
        }
        int mn = 1e18;
        for(int i = 1;i<=s;i++) {
            if(dist[a[i]]!=inf) {
                mn = min(mn,dist[a[i]]);
            }
        }
        if(mn == 1e18) {
            cout << "oo\n";
        } else {
            cout << mn << "\n";
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--) {
        solve();
    }





    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41