Submission #1327371

#TimeUsernameProblemLanguageResultExecution timeMemory
1327371herissonwowwValley (BOI19_valley)C++20
36 / 100
3095 ms7512 KiB
#include <iostream>
#include <vector>
#include <array>
#include <climits>
using namespace std;
const int N = 1e5+5;
const long long INF = 1e18 + 5;
bool shops[N];
vector<array<int, 3> > g[N];
int e, n, s, q;
long long dfs(int u, int p, int blocked, long long curd = 0){
    if(u==e)
        return -1;
    if(u == e)
        return -1;
    long long dist = (shops[u] ? curd : INF);

    for(auto [v, w, id] : g[u]){
        if(id==blocked||v==p)
            continue;
        dist = min(dist, dfs(v,u,blocked, curd+w));
    }
    return dist;
}
int main()
{
    //ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> s >> q >> e;
    for(int i = 1; i < n; i++){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w, i});
        g[v].push_back({u, w, i});
    }
    for(int i = 0; i < s; i++){
        int c; cin >> c;
        shops[c] = 1;
    }
    while(q--){
        int i, r; cin >> i >> r;
        long long res = dfs(r,r,i);
        if(res == -1)
            cout << "escaped\n";
        else if (res == INF)
            cout << "oo\n";
        else
            cout << res << '\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...