제출 #1328601

#제출 시각아이디문제언어결과실행 시간메모리
1328601tkm_algorithmsValley (BOI19_valley)C++20
32 / 100
72 ms20352 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;
const int NMAX = 1e5+10;
const int inf = 5e3*1e9+10;
struct edge{
	int v, w, id;
};

P E[NMAX];
vector<edge> g[NMAX];
int tin[NMAX], tout[NMAX];
int d[NMAX], s[NMAX], opt[NMAX];
int t = 0;

void dfs(int nd, int p = -1, int v = -1) {
	tin[nd] = t++, opt[nd] = v;
	for (auto ch: g[nd]) {
		if (ch.v == p)continue;
		E[ch.id] = {nd, ch.v};
		s[ch.v] = s[nd]+ch.w;
		dfs(ch.v, nd, (d[nd] == 0?nd:v));
		d[nd] = min(d[nd], d[ch.v]+ch.w);
	}
	
	tout[nd] = t-1;
}

bool f(int l, int r, int x) {
	if (l <= x && x <= r)return 1;
	return 0;
}

void solve() {
	int n, ss, q, e;
	cin >> n >> ss >> q >> e;
	
	rep(i, 1, n+1)d[i] = inf;
	rep(i, 1, n) {
		int u, v, w; cin >> u >> v >> w;
		g[u].push_back({v, w, i});
		g[v].push_back({u, w, i});
	}
	
	rep(i, 0, ss) {
		int c; cin >> c;
		d[c] = 0;
	}
	
	dfs(e);
	
	while (q--) {
		int I, R; cin >> I >> R;
		int v = E[I].second;
		int a = f(tin[v], tout[v], tin[R]);
		if (!a)cout << "escaped\n";
		else {
			int uc = inf;
			if (opt[R] != -1 && f(tin[v], tout[v], tin[opt[R]]))uc = s[R]-s[opt[R]];
			int res = min(d[R], min(d[v]+s[R]-s[v], uc));
			if (res == inf)cout << "oo" << nl;
			else cout << res << nl;
		}
	}	
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    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...