This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 1e6 + 5, lg = 22;
vector<pair<ll, ll>> g[N];
ll need[N], comp[N], depth[N], up[lg][N];
ll vals[lg], dp[1 << lg][lg];
void dfs(ll v, ll par = 0)
{
up[0][v] = par;
for (ll i = 1; i < lg; i++)
up[i][v] = up[i - 1][up[i - 1][v]];
for (auto [to, w] : g[v])
if (to != par)
{
if (w != 0)
need[to] = need[v] | (1 << comp[w]);
else need[to] = need[v];
depth[to] = depth[v] + 1;
dfs(to, v);
}
}
ll lca(ll a, ll b)
{
if (depth[a] < depth[b])
swap(a, b);
for (ll bit = lg - 1; bit >= 0; bit--)
if (depth[a] - (1 << bit) >= depth[b])
a = up[bit][a];
if (a == b)
return a;
for (ll bit = lg - 1; bit >= 0; bit--) if (up[bit][a] != up[bit][b]) a = up[bit][a], b = up[bit][b];
return up[0][a];
}
ll dist(ll a, ll b)
{
return depth[a] + depth[b] - depth[lca(a, b)] * 2;
}
void solve()
{
ll n;
cin >> n;
ll s, t;
cin >> s >> t;
array<ll, 3> e[n - 1];
for (ll i = 0; i < n - 1; i++)
{
cin >> e[i][0] >> e[i][1] >> e[i][2];
g[e[i][0]].push_back(make_pair(e[i][1], e[i][2]));
g[e[i][1]].push_back(make_pair(e[i][0], e[i][2]));
}
ll sz = 0;
{
set<ll> tmp;
for (ll i = 1; i <= n; i++)
for (auto [j, w] : g[i])
if (w)
tmp.insert(w);
tmp.insert(s);
tmp.insert(t);
for (ll i : tmp) comp[i] = sz, vals[sz++] = i;
}
dfs(s, s);
ll dp[1 << sz][sz];
for (ll i = 0; i < (1 << sz); i++)
for (ll j = 0; j < sz; j++)
dp[i][j] = 1e18;
dp[1 << comp[s]][comp[s]] = 0;
for (ll msk = 0; msk < (1 << sz); msk++) if (msk != (1 << comp[s]))
{
for (ll i = 0; i < sz; i++)
if (msk >> i & 1 and ((msk ^ (1 << i)) & need[vals[i]]) == need[vals[i]])
for (ll j = 0; j < sz; j++)
if ((msk >> j & 1) and j != i)
dp[msk][i] = min(dp[msk][i], dp[msk ^ (1 << i)][j] + dist(vals[i], vals[j]));
}
ll ans = 1e18;
for (ll msk = 0; msk < (1 << sz); msk++)
ans = min(ans, dp[msk][comp[t]]);
if (ans == 1e18)
ans = -1;
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t = 1;
// precomp();
// cin >> t;
for (ll cs = 1; cs <= t; cs++)
solve();
// cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |