제출 #1327363

#제출 시각아이디문제언어결과실행 시간메모리
1327363herissonwowwValley (BOI19_valley)C++20
0 / 100
35 ms7508 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;
    long long dist;
    if(shops[u])
        dist = curd;
    else
        dist = 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;
    }
    if(n<=1000 && q<=1000){
        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...