#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
#define mins(a, b) (a = min(a,b))
const int MXN = 1e6+2, MXM = 20, inf = 1e9;
int n, m, s, t;
vector<pii> g[MXN];
int dis[MXM+1][MXN], dp[1<<MXM][MXM], id[MXN], mask[MXM+1][MXN];
vector<int> vec;
void dfs(int wh, int v, int p=0) {
for(auto [u, w] : g[v])
if(u!=p) {
dis[wh][u] = dis[wh][v]+1;
mask[wh][u] = mask[wh][v] | (w ? (1<<id[w]) : 0);
dfs(wh, u, v);
}
}
inline bool is_sub(int x, int y) { return (x&y)==x; }
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> s >> t;
for(int i=0, u,v,w; i<n-1; i++) {
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
if(w) vec.push_back(w);
}
sort(vec.begin(), vec.end());
m = unique(vec.begin(), vec.end())-vec.begin();
vec.resize(m);
for(int i=0; i<m; i++) id[vec[i]] = i;
for(int i=0; i<m; i++) dfs(i, vec[i]);
dfs(m, s);
if(!mask[m][t]) {
cout << dis[m][t] << '\n';
return 0;
}
for(int msk=0; msk<(1<<m); msk++)
fill(dp[msk], dp[msk]+m, inf);
for(int i=0; i<m; i++)
if(!mask[m][vec[i]])
dp[1<<i][i] = dis[m][vec[i]];
for(int msk=1; msk<(1<<m)-1; msk++)
for(int i=0; i<m; i++) if(msk>>i&1)
for(int j=0; j<m; j++) if(!(msk>>j&1))
if(is_sub(mask[i][vec[j]], msk))
mins(dp[msk^(1<<j)][j], dp[msk][i] + dis[i][vec[j]]);
int ans = inf;
for(int msk=1; msk<(1<<m); msk++)
for(int i=0; i<m; i++) if((msk>>i&1) && is_sub(mask[i][t], msk))
mins(ans, dp[msk][i] + dis[i][t]);
cout << (ans==inf ? -1 : ans) << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |