제출 #1327367

#제출 시각아이디문제언어결과실행 시간메모리
1327367kitijakValley (BOI19_valley)C++20
36 / 100
3094 ms7512 KiB
#include <iostream>
#include<algorithm>
#include <vector>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll INF=1e18+5;
    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=INF;
    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==(ll)-1)
            cout << "escaped";
        else if(mn==INF)
            cout << "oo";
        else
            cout << mn;
        cout << endl;
    }
    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...