제출 #1327326

#제출 시각아이디문제언어결과실행 시간메모리
1327326andy_vokizValley (BOI19_valley)C++20
36 / 100
3094 ms12252 KiB
#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);

using namespace std;
bool dfs(int i, int p, pair<int, int> snow, vector<vector<pair<int, int>>>& adj, int e, long long& dist, set<int>& shops, long long& minn){
    if(i == e){
        return true;
    }
    if(shops.count(i)){
        minn = min(minn, dist);
    }
    int ok = false;
    for(auto u : adj[i]){
        int j = u.first;
        int c = u.second;
        if(j == p){
            continue;
        }
        if((i == snow.first && j == snow.second) || (j == snow.first && i == snow.second)){
            continue;
        }
        dist += c;
        bool b = dfs(j, i, snow, adj, e, dist, shops, minn);
        if(b){
            ok = true;
        }
        dist -= c;
    }
    return ok;
}
int main()
{
    fio
    int n, s, q, e;
    cin >> n >> s >> q >> e;
    vector<vector<pair<int, int>>> adj(n+1);
    vector<pair<int, int>> roads(n+1);
    for(int i = 0; i < n-1; ++i){
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
        roads[i+1] = {a, b};
    }
    set<int> shops;
    for(int i = 0; i< s; ++i){
        int c;
        cin >> c;
        shops.insert(c);
    }
    for(int qw = 0; qw < q; ++qw){
        int r, vil;
        cin >> r >> vil;
        long long dist = 0;
        long long minn = LLONG_MAX;
        if(dfs(vil, -1, roads[r], adj, e, dist, shops, minn)){
            cout << "escaped\n";
        }else{
            if(minn == LLONG_MAX){
                cout << "oo\n";
            }else{
                cout << minn << "\n";
            }
        }
    }
    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...