제출 #1307939

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307939		shisp1	Valley (BOI19_valley)	C++20	36 / 100	3095 ms	27972 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";
        }
        else {
            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";
            }
        }
        g[uu].insert({vv,ww});
        g[vv].insert({uu,ww});
    }
}
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: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41