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>
using namespace std;
const int N = 1e6;
int n, m, s, t, val[N], d[22][N], r[22][N];
int dp[1 << 20][20], key[22], num[22], door[22], distDoor[22], reqDoor[22], dist[22][22], req[22][22];
vector<pair<int, int>> adj[N];
void Dfs(int u, int p, int keyInd) {
for(auto e : adj[u]) {
int v = e.first;
int ind = e.second;
if (v == p)
continue;
r[keyInd][v] = r[keyInd][u] | val[ind];
d[keyInd][v] = d[keyInd][u] + 1;
if (keyInd != -1 && val[ind] == (1 << keyInd)) {
door[keyInd] = u;
distDoor[keyInd] = d[keyInd][u];
reqDoor[keyInd] = r[keyInd][u];
}
Dfs(v, u, keyInd);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s >> t;
s--, t--;
for(int i = 0; i < n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--, w--;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
if (w >= 0) {
key[m] = w;
num[m] = i;
++m;
}
}
key[m] = s;
key[m + 1] = t;
door[m] = s;
door[m + 1] = t;
for(int i = 0; i < m; i++)
val[num[i]] = (1 << i);
for(int i = 0; i < m + 2; i++) {
Dfs(key[i], -1, i);
}
for(int i = 0; i < m + 2; i++)
for(int j = 0; j < m + 2; j++) {
dist[i][j] = d[j][door[i]] + distDoor[j];
req[i][j] = r[j][door[i]] | reqDoor[j];
}
int ans = (req[m][m + 1] == 0? dist[m][m + 1] : 1e9);
for(int mask = 0; mask < (1 << m); mask++)
for(int i = 0; i < m; i++)
dp[mask][i] = 1e9;
for(int i = 0; i < m; i++)
if (req[m][i] == 0)
dp[(1 << i)][i] = dist[m][i];
for(int mask = 0; mask < (1 << m); mask++)
for(int i = 0; i < m; i++) {
if (dp[mask][i] == 1e9)
continue;
if ((mask & req[i][m + 1]) == req[i][m + 1])
ans = min(ans, dp[mask][i] + dist[i][m + 1]);
for(int j = 0; j < m; j++)
if ((mask & req[i][j]) == req[i][j])
dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist[i][j]);
}
cout << (ans == 1e9? -1 : ans);
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... |