This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define pb push_back
#define debug(x) cerr << #x << " : " << x << endl;
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const ll N = 1e5+20,mod = 1e9+7;
int poww(int a,int k){
if (!k) return 1;
if (k == 1) return a;
int r = poww(a,k/2);
return 1ll*r*r%mod*poww(a,k&1)%mod;
}
int n,s,t;
vector<pll> adj[N];
int k[22],din[22],par[N][20],h[N],mark[N],din2[N],din3[N],din4[N];
vector<int> dp[N][22],out[22];
pll e[22];
bitset<N> vis;
void bfs(int v){
queue<int> q;
q.push(k[v]);
vis[k[v]] = 1;
while (!q.empty()){
int u = q.front();
q.pop();
for (pll w : adj[u]){
if (vis[w.X]) continue;
vis[w.X] = 1;
q.push(w.X);
for (int x : dp[u][v])
dp[w.X][v].pb(x);
if (w.Y)
dp[w.X][v].pb(w.Y);
if (u == t && v != 21) dp[w.X][v].pb(21);
}
}
vis.reset();
}
bool pre(int v){
mark[v] = 1;
din[v] = 0;
for (int u : dp[s][v]){
din[v]++;
out[u].pb(v);
if (mark[u] == 1)
return 0;
if (mark[u] == 2) continue;
if (!pre(u)) return 0;
}
for(int u : dp[e[v].X][v]){
if (u != v){
out[u].pb(v);
din[v]++;
if (mark[u] == 1) return 0;
if (!mark[u] && !pre(u)) return 0;
}
}
for(int u : dp[e[v].Y][v]){
if (u != v){
out[u].pb(v);
din[v]++;
if (mark[u] == 1) return 0;
if (!mark[u] && !pre(u)) return 0;
}
}
mark[v] = 2;
return 1;
}
void dfs(int v,int p){
for (pll u : adj[v]){
if (u.X == p) continue;
h[u.X] = h[v]+1;
par[u.X][0] = v;
dfs(u.X,v);
}
}
inline int lca(int u,int v){
if (h[u] > h[v]) swap(u,v);
repr(i,18,0)
if (h[v]-h[u] >= (1 << i))
v = par[v][i];
if (u == v) return u;
repr(i,18,0){
if (par[v][i] != par[u][i]){
v = par[v][i];
u = par[u][i];
}
}
return par[v][0];
}
inline int dist(int u,int v){
int w = lca(u,v);
return h[v]+h[u]-2*h[w];
}
int main(){
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
memset(din,-1,sizeof din);
int cnt = 0;
cin >> n >> s >> t;
rep(i,1,n){
int u,v,w;
cin >> u >> v >> w;
if (!w){
adj[u].pb({v,0});
adj[v].pb({u,0});
}
else{
cnt++;
k[cnt] = w;
e[cnt] = {u,v};
adj[u].pb({v,cnt});
adj[v].pb({u,cnt});
}
}
k[21] = t;
rep(i,1,cnt+1) bfs(i);
bfs(21);
e[21] = {t,t};
if (!pre(21)){
cout << -1;
return 0;
}
vector<int> ve,ve2,ve3,ve4;
dfs(1,-1);
rep(j,1,19){
rep(i,2,n+1){
if (h[i] < (1 << j)) continue;
par[i][j] = par[par[i][j-1]][j-1];
}
}
if (!din[21]){
cout << dist(s,t);
return 0;
}
queue<int> q;
stack<int> st;
priority_queue<pll> pq,pq2;
rep(i,1,cnt+1){
din2[i] = din3[i] = din4[i] = din[i];
if (!din[i]){
q.push(i);
st.push(i);
pq.push({dist(e[i].X,t),i});
pq2.push({max(dist(e[i].X,t),dist(e[i].Y,t)),i});
}
}
din2[21] = din3[21] = din4[21] = din[21];
while (!q.empty()){
int v = q.front();
q.pop();
ve.pb(v);
for (int u : out[v]){
din[u]--;
if (!din[u]) q.push(u);
}
}
while (!st.empty()){
int v = st.top();
st.pop();
ve2.pb(v);
for (int u : out[v]){
din2[u]--;
if (!din2[u]) st.push(u);
}
}
while (!pq.empty()){
int v = pq.top().Y;
pq.pop();
ve3.pb(v);
for (int u : out[v]){
din3[u]--;
if (!din3[u]) pq.push({dist(t,e[u].X),u});
}
}
while (!pq2.empty()){
int v = pq2.top().Y;
pq2.pop();
ve4.pb(v);
for (int u : out[v]){
din4[u]--;
if (!din4[u]) pq2.push({max(dist(t,e[u].Y),dist(t,e[u].X)),u});
}
}
int v = s,p = 0;
ll ans = 0,ans2 = 0,ans3 = 0,ans4 = 0;
while (v != t){
int u = ve[p];
if (u == 21){
ans += dist(v,t);
break;
}
ans += dist(v,k[u]);
int w1 = dist(k[u],e[u].X),w2 = dist(k[u],e[u].Y);
if (w1 <= w2){
v = e[u].X;
ans += w1;
}
else{
v = e[u].Y;
ans+=w2;
}
p++;
}
v = s,p = 0;
while (v != t){
int u = ve2[p];
if (u == 21){
ans2 += dist(v,t);
break;
}
ans2 += dist(v,k[u]);
int w1 = dist(k[u],e[u].X),w2 = dist(k[u],e[u].Y);
if (w1 <= w2){
v = e[u].X;
ans2 += w1;
}
else{
v = e[u].Y;
ans2 += w2;
}
p++;
}
v = s, p = 0;
while (v != t){
int u = ve3[p];
if (u == 21){
ans3 += dist(v,t);
break;
}
ans3 += dist(v,k[u]);
int w1 = dist(k[u],e[u].X),w2 = dist(k[u],e[u].Y);
if (w1 <= w2){
v = e[u].X;
ans3 += w1;
}
else{
v = e[u].Y;
ans3 += w2;
}
p++;
}
v = s, p =0;
while (v != t){
int u = ve4[p];
if (u == 21){
ans4 += dist(v,t);
break;
}
ans4 += dist(v,k[u]);
int w1 = dist(k[u],e[u].X),w2 = dist(k[u],e[u].Y);
if (w1 <= w2){
v = e[u].X;
ans4 += w1;
}
else{
v = e[u].Y;
ans4 += w2;
}
p++;
}
cout << min({ans3,ans,ans2,ans4});
}
Compilation message (stderr)
Main.cpp:10:9: error: 'pair' does not name a type
10 | typedef pair<int,int> pll;
| ^~~~
Main.cpp:20:1: error: 'vector' does not name a type
20 | vector<pll> adj[N];
| ^~~~~~
Main.cpp:22:1: error: 'vector' does not name a type
22 | vector<int> dp[N][22],out[22];
| ^~~~~~
Main.cpp:23:1: error: 'pll' does not name a type; did you mean 'll'?
23 | pll e[22];
| ^~~
| ll
Main.cpp:24:1: error: 'bitset' does not name a type
24 | bitset<N> vis;
| ^~~~~~
Main.cpp: In function 'void bfs(int)':
Main.cpp:26:5: error: 'queue' was not declared in this scope
26 | queue<int> q;
| ^~~~~
Main.cpp:1:1: note: 'std::queue' is defined in header '<queue>'; did you forget to '#include <queue>'?
+++ |+#include <queue>
1 | #define rep(i,l,r) for (int i = l; i < r; i++)
Main.cpp:26:11: error: expected primary-expression before 'int'
26 | queue<int> q;
| ^~~
Main.cpp:27:5: error: 'q' was not declared in this scope
27 | q.push(k[v]);
| ^
Main.cpp:28:5: error: 'vis' was not declared in this scope
28 | vis[k[v]] = 1;
| ^~~
Main.cpp:32:14: error: 'pll' was not declared in this scope; did you mean 'll'?
32 | for (pll w : adj[u]){
| ^~~
| ll
Main.cpp:42:5: error: expected primary-expression before '}' token
42 | }
| ^
Main.cpp:41:10: error: expected ';' before '}' token
41 | }
| ^
| ;
42 | }
| ~
Main.cpp:42:5: error: expected primary-expression before '}' token
42 | }
| ^
Main.cpp:41:10: error: expected ')' before '}' token
41 | }
| ^
| )
42 | }
| ~
Main.cpp:32:13: note: to match this '('
32 | for (pll w : adj[u]){
| ^
Main.cpp:42:5: error: expected primary-expression before '}' token
42 | }
| ^
Main.cpp:30:13: warning: unused variable 'u' [-Wunused-variable]
30 | int u = q.front();
| ^
Main.cpp: In function 'bool pre(int)':
Main.cpp:48:18: error: 'dp' was not declared in this scope
48 | for (int u : dp[s][v]){
| ^~
Main.cpp:50:9: error: 'out' was not declared in this scope
50 | out[u].pb(v);
| ^~~
Main.cpp:56:17: error: 'dp' was not declared in this scope
56 | for(int u : dp[e[v].X][v]){
| ^~
Main.cpp:56:20: error: 'e' was not declared in this scope
56 | for(int u : dp[e[v].X][v]){
| ^
Main.cpp:58:13: error: 'out' was not declared in this scope
58 | out[u].pb(v);
| ^~~
Main.cpp:64:17: error: 'dp' was not declared in this scope
64 | for(int u : dp[e[v].Y][v]){
| ^~
Main.cpp:64:20: error: 'e' was not declared in this scope
64 | for(int u : dp[e[v].Y][v]){
| ^
Main.cpp:66:13: error: 'out' was not declared in this scope
66 | out[u].pb(v);
| ^~~
Main.cpp: In function 'void dfs(int, int)':
Main.cpp:76:10: error: 'pll' was not declared in this scope; did you mean 'll'?
76 | for (pll u : adj[v]){
| ^~~
| ll
Main.cpp:82:1: error: expected primary-expression before '}' token
82 | }
| ^
Main.cpp:81:6: error: expected ';' before '}' token
81 | }
| ^
| ;
82 | }
| ~
Main.cpp:82:1: error: expected primary-expression before '}' token
82 | }
| ^
Main.cpp:81:6: error: expected ')' before '}' token
81 | }
| ^
| )
82 | }
| ~
Main.cpp:76:9: note: to match this '('
76 | for (pll u : adj[v]){
| ^
Main.cpp:82:1: error: expected primary-expression before '}' token
82 | }
| ^
Main.cpp: In function 'int lca(int, int)':
Main.cpp:84:22: error: 'swap' was not declared in this scope
84 | if (h[u] > h[v]) swap(u,v);
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:102:5: error: 'ios' has not been declared
102 | ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
| ^~~
Main.cpp:102:32: error: 'cin' was not declared in this scope
102 | ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
| ^~~
Main.cpp:1:1: note: 'std::cin' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
+++ |+#include <iostream>
1 | #define rep(i,l,r) for (int i = l; i < r; i++)
Main.cpp:102:44: error: 'cout' was not declared in this scope
102 | ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
| ^~~~
Main.cpp:102:44: note: 'std::cout' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
Main.cpp:103:5: error: 'memset' was not declared in this scope
103 | memset(din,-1,sizeof din);
| ^~~~~~
Main.cpp:1:1: note: 'memset' is defined in header '<cstring>'; did you forget to '#include <cstring>'?
+++ |+#include <cstring>
1 | #define rep(i,l,r) for (int i = l; i < r; i++)
Main.cpp:110:13: error: 'adj' was not declared in this scope
110 | adj[u].pb({v,0});
| ^~~
Main.cpp:116:13: error: 'e' was not declared in this scope
116 | e[cnt] = {u,v};
| ^
Main.cpp:117:13: error: 'adj' was not declared in this scope
117 | adj[u].pb({v,cnt});
| ^~~
Main.cpp:124:5: error: 'e' was not declared in this scope
124 | e[21] = {t,t};
| ^
Main.cpp:129:5: error: 'vector' was not declared in this scope
129 | vector<int> ve,ve2,ve3,ve4;
| ^~~~~~
Main.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
+++ |+#include <vector>
1 | #define rep(i,l,r) for (int i = l; i < r; i++)
Main.cpp:129:12: error: expected primary-expression before 'int'
129 | vector<int> ve,ve2,ve3,ve4;
| ^~~
Main.cpp:141:5: error: 'queue' was not declared in this scope
141 | queue<int> q;
| ^~~~~
Main.cpp:141:5: note: 'std::queue' is defined in header '<queue>'; did you forget to '#include <queue>'?
Main.cpp:141:11: error: expected primary-expression before 'int'
141 | queue<int> q;
| ^~~
Main.cpp:142:5: error: 'stack' was not declared in this scope
142 | stack<int> st;
| ^~~~~
Main.cpp:1:1: note: 'std::stack' is defined in header '<stack>'; did you forget to '#include <stack>'?
+++ |+#include <stack>
1 | #define rep(i,l,r) for (int i = l; i < r; i++)
Main.cpp:142:11: error: expected primary-expression before 'int'
142 | stack<int> st;
| ^~~
Main.cpp:143:5: error: 'priority_queue' was not declared in this scope
143 | priority_queue<pll> pq,pq2;
| ^~~~~~~~~~~~~~
Main.cpp:143:5: note: 'std::priority_queue' is defined in header '<queue>'; did you forget to '#include <queue>'?
Main.cpp:143:20: error: 'pll' was not declared in this scope; did you mean 'll'?
143 | priority_queue<pll> pq,pq2;
| ^~~
| ll
Main.cpp:143:25: error: 'pq' was not declared in this scope; did you mean 'pb'?
143 | priority_queue<pll> pq,pq2;
| ^~
| pb
Main.cpp:143:28: error: 'pq2' was not declared in this scope
143 | priority_queue<pll> pq,pq2;
| ^~~
Main.cpp:147:13: error: 'q' was not declared in this scope
147 | q.push(i);
| ^
Main.cpp:148:13: error: 'st' was not declared in this scope; did you mean 't'?
148 | st.push(i);
| ^~
| t
Main.cpp:150:23: error: 'max' was not declared in this scope
150 | pq2.push({max(dist(e[i].X,t),dist(e[i].Y,t)),i});
| ^~~
Main.cpp:154:13: error: 'q' was not declared in this scope
154 | while (!q.empty()){
| ^
Main.cpp:157:9: error: 've' was not declared in this scope; did you mean 'v'?
157 | ve.pb(v);
| ^~
| v
Main.cpp:158:22: error: 'out' was not declared in this scope
158 | for (int u : out[v]){
| ^~~
Main.cpp:163:13: error: 'st' was not declared in this scope; did you mean 't'?
163 | while (!st.empty()){
| ^~
| t
Main.cpp:166:9: error: 've2' was not declared in this scope
166 | ve2.pb(v);
| ^~~
Main.cpp:167:22: error: 'out' was not declared in this scope
167 | for (int u : out[v]){
| ^~~
Main.cpp:175:9: error: 've3' was not declared in this scope
175 | ve3.pb(v);
| ^~~
Main.cpp:176:22: error: 'out' was not declared in this scope
176 | for (int u : out[v]){
| ^~~
Main.cpp:184:9: error: 've4' was not declared in this scope
184 | ve4.pb(v);
| ^~~
Main.cpp:185:22: error: 'out' was not declared in this scope
185 | for (int u : out[v]){
| ^~~
Main.cpp:187:37: error: 'max' was not declared in this scope
187 | if (!din4[u]) pq2.push({max(dist(t,e[u].Y),dist(t,e[u].X)),u});
| ^~~
Main.cpp:193:17: error: 've' was not declared in this scope; did you mean 'v'?
193 | int u = ve[p];
| ^~
| v
Main.cpp:200:19: error: 'w2' was not declared in this scope; did you mean 'w1'?
200 | if (w1 <= w2){
| ^~
| w1
Main.cpp:212:17: error: 've2' was not declared in this scope
212 | int u = ve2[p];
| ^~~
Main.cpp:219:19: error: 'w2' was not declared in this scope; did you mean 'w1'?
219 | if (w1 <= w2){
| ^~
| w1
Main.cpp:231:17: error: 've3' was not declared in this scope
231 | int u = ve3[p];
| ^~~
Main.cpp:238:19: error: 'w2' was not declared in this scope; did you mean 'w1'?
238 | if (w1 <= w2){
| ^~
| w1
Main.cpp:250:17: error: 've4' was not declared in this scope
250 | int u = ve4[p];
| ^~~
Main.cpp:257:19: error: 'w2' was not declared in this scope; did you mean 'w1'?
257 | if (w1 <= w2){
| ^~
| w1
Main.cpp:267:13: error: 'min' was not declared in this scope; did you mean 'main'?
267 | cout << min({ans3,ans,ans2,ans4});
| ^~~
| main