Submission #1317197

#TimeUsernameProblemLanguageResultExecution timeMemory
1317197vaishakhvValley (BOI19_valley)C++20
9 / 100
12 ms496 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll cap = 1e2+1;
vector<pair<ll,ll>> adj[cap];

void dijkstra(){

}
int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

    ll n, s, q, e;
    cin >> n >> s >> q >> e;

    vector<tuple<ll,ll,ll>> edges;
    for (ll i{}; i < n-1; i++){
        ll a, b, w; cin >> a >> b >> w;
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
        edges.push_back({a,b,w});
    }   

    vector<ll> shops;

    for (ll i{}; i < s; i++){
        ll c; cin >> c;
        shops.push_back(c);
    }

    for (ll i{}; i < q; i++){
        ll I, r; cin >> I >> r;
        ll a, b, w; tie(a, b, w) = edges[I-1];
        erase(adj[a], make_pair(b, w));
        erase(adj[b], make_pair(a, w));

        priority_queue<pair<ll,ll>> pq;
        vector<bool> visited(n+1, false);
        vector<ll> dist(n+1, 1e18);

        dist[r] = 0;
        pq.push({0, r});

        while (!pq.empty()){
            auto t = pq.top(); pq.pop();
            ll d = -t.first;
            ll v = t.second;

            if (visited[v]) continue;
            visited[v] = true;

            for (auto pr : adj[v]){
                ll u = pr.first;
                ll wt = pr.second;

                if (dist[u] > d + wt){
                    dist[u] = d + wt;
                    pq.push({-dist[u], u});
                }
            }
        }

        if (dist[e] == 1e18) {
            ll ans = 1e18;
            for (ll v : shops) {
                ans = min(ans, dist[v]);
            }

            if (ans == 1e18) {
                cout << "oo\n";
            } else {
                cout << ans << "\n";
            }
        } else {
            cout << "escaped\n";
        }


        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...