Submission #1327358

#TimeUsernameProblemLanguageResultExecution timeMemory
1327358kitijakValley (BOI19_valley)C++20
0 / 100
3093 ms7528 KiB
#include <iostream>
#include<algorithm>
#include <vector>
#include <climits>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
    ll n, s, q, e, u, v, w;
    vector<pair<pair<int, int>, int>>graph[100005];
    vector<pair<int, int>>edge;
    bool shop[100005];
ll dfs(int x, int p, int road, ll d){
    if(x==e){
        return -1;
    }
    ll dist=INT_MAX;
    if(shop[x])
        dist=d;
    for(auto y : graph[x]){
        if(y.se!=road && y.fi.fi!=p){
            dist=min(dist, dfs(y.fi.fi, x, road, d+y.fi.se));
        }

    }
    return dist;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s >> q >> e;
    for(int i=1; i<n; i++){
        cin >> u >> v >> w;
        graph[u].pb({{v, w}, i});
        graph[v].pb({{u, w}, i});
    }
    for(int i=0; i<s; i++){
        cin >> u;
        shop[u]=1;
    }
    while(q--){
        cin >> u >> v;
        ll mn=dfs(v, v, u, 0LL);
        if(mn==-1)
            cout << "escaped\n";
        else if(mn==INT_MAX)
            cout << "oo\n";
        else
            cout << mn << '\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...