⚙️AlgorithmIntermediate

Bidirectional BFS (Meet in the Middle Search)

Key Points

•
Bidirectional BFS searches forward from the start and backward from the goal to meet in the middle, drastically reducing explored states.
•
In unweighted graphs, it guarantees the shortest path just like normal BFS but usually explores far fewer nodes.
•
The expected work drops from O( $b^{d}$ ) to about O( $b^{d /2}$ ) where b is branching factor and d is shortest path length.
•
You maintain two queues (frontiers), two distance/parent maps, and stop as soon as the frontiers intersect.
•
For weighted graphs with non-negative weights, use bidirectional Dijkstra with a careful termination rule based on current best meeting distance.
•
It works best when the branching factors are similar in both directions and the goal is known.
•
Memory usage also improves from O( $b^{d}$ ) to O( $b^{d /2}$ ) because you store only mid-depth frontiers.
•
Common pitfalls include incorrect meeting/termination conditions, mismanaged parent arrays, and forgetting to reverse edges for backward search on directed graphs.

Prerequisites

→Graphs and adjacency lists — You must represent graphs efficiently to traverse neighbors during BFS/Dijkstra.
→Breadth-First Search (BFS) — Bidirectional BFS is built on BFS layering and visited/parent tracking.
→Dijkstra’s algorithm — The weighted variant uses two Dijkstra searches with a careful termination rule.
→Queues and priority queues — BFS requires a FIFO queue; Dijkstra requires a min-heap for tentative distances.
→Path reconstruction — Combining forward and backward parents at the meeting node yields the final path.
→Big-O notation — Understanding O(b^d) versus O(b^{d/2}) motivates the algorithm’s benefit.
→Directed vs. undirected graphs — Backward search on directed graphs needs the reverse graph.
→Non-negative edge weights — Required by Dijkstra to ensure correctness and termination conditions.

Detailed Explanation

Tap terms for definitions

01Overview

Bidirectional BFS (also called meet-in-the-middle search) is a shortest-path technique that launches two simultaneous searches: one from the source and one from the target. Instead of pushing one wave of exploration all the way across the graph, you push two smaller waves until they touch. Because the number of nodes in a breadth-first wave typically grows exponentially with depth (for large, branching graphs), meeting halfway reduces the amount of work dramatically. The method preserves shortest-path guarantees in unweighted graphs since each wave expands level by level, and the first time the two visited regions intersect, you can reconstruct a globally shortest path. Practically, you maintain two BFS queues, two visited sets (or distance arrays), and two parent arrays for path reconstruction. You alternate expanding the smaller frontier to keep both sides balanced. Every time you discover a node that the other side has already visited, you have found a connecting point and can merge the partial paths into a full solution. For weighted graphs with non-negative weights, a parallel idea exists using Dijkstra’s algorithm from both ends, with a specific termination rule. Bidirectional BFS is widely used in maze solving, puzzle state-space search (like Word Ladder), and routing on large graphs where the destination is known.

02Intuition & Analogies

Imagine two hikers starting from opposite ends of a long tunnel. If only one hiker walks, it takes a long time to reach the other end. But if both start walking toward each other, they meet in the middle much sooner. Graph searches behave similarly: a BFS wave from one side expands like a balloon covering more and more nodes. Starting a second balloon from the goal lets the balloons touch when their radii sum to the full distance, so neither balloon needs to grow as large. If each step multiplies your options (branching factor), exploring d steps from one side requires checking many nodes. But exploring only d/2 steps from both sides shrinks the effort massively because exponential growth is sensitive to depth. A practical analogy is searching a library for a book located at a known shelf. Walking aisle by aisle from the entrance is slow; having a friend start from the known shelf location and walking toward you turns the task into two smaller searches that converge. The moment you see each other, you know the shortest route between the entrance and the shelf: just take the path you walked plus the path your friend walked. The same idea extends to road networks (drive from home and from the destination until routes overlap) and puzzle-solving (expand valid moves from both initial and goal configurations). The key ingredients are: two synchronized searches, a rule to alternate expansions fairly, and a quick check to detect when the two explored regions intersect.

03Formal Definition

Given a graph G = (V, E), a source s, and a target t, bidirectional BFS performs simultaneous searches from s (forward) and from t (backward). In unweighted graphs (or equally weighted edges), BFS expands in layers of increasing distance. Maintain two queues

Q_{f}

and

Q_{b}

, two distance arrays

d_{f}

and

d_{b}

, and two predecessor arrays

c_{f}

and

c_{b}

. Initialize

d_{f}

[s] = 0,

d_{b}

[t] = 0, and others to 6c696e6674y. At each iteration, choose one side (often the queue with fewer nodes) and expand exactly one BFS layer: for each vertex u in the current frontier, relax all edges (u, v), setting

d_{f}

[v] =

d_{f}

[u] + 1 (or similarly for the backward direction) if v is newly discovered. If v is already discovered by the opposite search (

d_{b}

[v] < 6c696e6674y), an intersection is found; one can reconstruct a shortest path by combining s 192 v via

c_{f}

and v 192 t via

c_{b}

. For weighted graphs with non-negative weights, replace BFS with Dijkstra on G and on the reverse graph

G^{R}

. Maintain tentative distances

d_{f}

and

d_{b}

, two min-heaps, and a best meeting distance b4 =

min_{v \in V}

(

d_{f}

[v] +

d_{b}

[v]). Stop when the minimum keys at the tops of the heaps satisfy

\minKey

(

Q_{f}

) +

\minKey

(

Q_{b}

)

\geq

b4, ensuring optimality.

04When to Use

Use bidirectional BFS when the goal node is known and there is a unique or sparse set of targets, particularly in large, unweighted or uniformly weighted graphs where breadth-first layers grow quickly. Examples include: (1) Maze or grid shortest paths when the start and end cells are given; (2) Word Ladder puzzles where transformations proceed by single-character edits and you know the target word; (3) Routing in social or road networks where you know the destination; and (4) State-space searches where reverse moves are easy to generate (e.g., 15-puzzle if you can invert moves). For weighted graphs with non-negative weights (e.g., road networks with distances), bidirectional Dijkstra is a good choice when you can build a reverse graph and when heuristics (like A*) are not available or admissible. It is especially attractive when branching factors are similar in both directions and the shortest-path depth is large because the savings grow with depth. Avoid it when the target is unknown, when reverse neighbors are hard or expensive to generate (e.g., one-way constraints without a precomputed reverse graph), or when branching is extremely unbalanced.

⚠️Common Mistakes

Not expanding whole BFS layers: In unweighted graphs, expanding only part of a layer can break shortest-path guarantees. Always process the entire current frontier from one side before checking for a meeting.
Incorrect meeting detection: Only declare success when a newly discovered node is already visited by the other side. Using a stale node or mixing parent arrays can yield wrong paths.
Mixing parent arrays: Keep separate predecessor arrays for forward and backward searches. During reconstruction, traverse c_f from the meeting node back to s, and c_b from the meeting node back to t (then reverse one side).
Forgetting reverse graph for directed/weighted cases: Backward search on a directed graph must run on the reverse graph G^R; otherwise, you may find paths that donbc0t exist.
Wrong termination in bidirectional Dijkstra: Stopping when the two visited sets first intersect can be suboptimal. Use the criterion \minKey(Q_f) + \minKey(Q_b) \ge \text{best} to ensure optimality.
Unbalanced expansion: Always expand the side with the smaller frontier (BFS) or smaller current key (Dijkstra) to reduce work.
High memory spikes: Although memory is reduced asymptotically, store only what you need (distances, parents, visited flags) to avoid unnecessary overhead.

Key Formulas

Single-direction BFS search size

O (b^{d})

Explanation: In graphs with branching factor b and shortest-path depth d, the number of explored nodes grows roughly exponentially with depth. This expresses the typical work of a one-ended BFS.

Bidirectional expansion per side

O (b^{d /2})

Explanation: Each of the two searches explores only about d/2 layers, yielding exponential savings. Total work is about 2\, $b^{d /2}$ , which is much smaller than $b^{d}$ for large d.

Meet-in-the-middle advantage

Total work \approx 2 b^{d /2} ≪ b^{d}

Explanation: Comparing 2 times b to the d/2 versus b to the d shows the savings. Since exponential growth is sensitive to depth, halving depth gives huge reductions.

Bidirectional Dijkstra stopping rule

min Key (Q_{f}) + min Key (Q_{b}) \geq v \in V min {d_{f} [v] + d_{b} [v]}

Explanation: Stop when the sum of the smallest tentative distances remaining in both queues cannot improve the current best meeting distance. This ensures optimality when all weights are non-negative.

Best meeting distance

δ^{*} = v \in V min {d_{f} [v] + d_{b} [v]}

Explanation: The shortest s192t path length equals the minimum over all vertices of forward distance to v plus backward distance from v to t. The algorithm maintains and tightens this bound.

Size of BFS tree up to depth d

i = 0 \sum d b^{i} = \frac{b ^{d + 1} - 1}{b - 1}

Explanation: This geometric series approximates the number of nodes within d layers when each node has about b children. It helps quantify the frontier size and memory usage.

BFS time complexity

O (n + m)

Explanation: Breadth-first search runs linear in nodes plus edges for adjacency lists. Bidirectional BFS still touches each discovered edge/vertex once per direction until meeting.

Dijkstra complexity

O ((n + m) lo g n)

Explanation: Using a binary heap, Dijkstra runs in O((n+m) log n). Running it bidirectionally does not change the asymptotic bound but reduces explored states in practice.

Complexity Analysis

In a uniform branching model with branching factor b and shortest path depth d, a one-ended BFS explores roughly

\sum_{i = 0}^{d}

b^{i}

\frac{b ^{d + 1} - 1}{b - 1}

nodes, commonly summarized as O(

b^{d}

). Bidirectional BFS reduces the explored depth to about d/2 on each side, so each side explores

\sum_{i = 0}^{⌊ d /2 ⌋}

b^{i} = O (b^{d /2}

). The total is approximately 2\,

b^{d /2}

, which is exponentially smaller than

b^{d}

when d is large. In adjacency-list graphs, each discovered edge is inspected at most once per direction until the meeting point, so the worst-case time is still O(n + m) for unweighted graphs, but the practical factor is reduced by early termination at depth d/2. Space usage follows the frontier size: instead of holding a frontier of size

Θ

(

b^{d}

), bidirectional BFS holds two frontiers of size

Θ

(

b^{d /2}

) each, for a total of O(

b^{d /2}

) memory, plus O(n) for bookkeeping in the worst case. For non-negative weighted graphs, bidirectional Dijkstra keeps two priority queues and two distance arrays. Asymptotically, the worst-case time remains O((n + m)

lo g

n) using binary heaps (or O(m + n

lo g

n) with Fibonacci heaps), but in practice, the number of relaxed edges before termination drops substantially because the meeting distance

δ

^* is often reached before either search settles the whole graph. The termination condition

\minKey

(

Q_{f}

) +

\minKey

(

Q_{b}

)

\geq

δ

^* ensures optimality. Space overhead includes two distance arrays, two parent arrays, two visited/settled flags, and two priority queues, typically O(n) plus the current frontier sizes. The memory advantage relative to a one-sided Dijkstra is again practical rather than asymptotic: fewer nodes are pushed/kept in the heaps when the meeting happens early.

Code Examples

Bidirectional BFS on an unweighted undirected graph with path reconstruction

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Bidirectional BFS for unweighted, undirected graphs.
5 // Reads: n m, then m edges (1-indexed or 0-indexed; we convert to 0-indexed here if needed), then s t (1-indexed).
6 // Outputs: shortest distance and one shortest path.
7 
8 static const int INF = 1e9;
9 
10 int main() {
11     ios::sync_with_stdio(false);
12     cin.tie(nullptr);
13 
14     int n, m;
15     if (!(cin >> n >> m)) return 0;
16     vector<vector<int>> g(n);
17     for (int i = 0; i < m; ++i) {
18         int u, v; cin >> u >> v;
19         // Assume input is 1-indexed; convert to 0-indexed
20         --u; --v;
21         g[u].push_back(v);
22         g[v].push_back(u);
23     }
24     int s, t; cin >> s >> t; --s; --t;
25 
26     if (s == t) {
27         cout << 0 << "\n" << (s+1) << "\n";
28         return 0;
29     }
30 
31     vector<int> distF(n, INF), distB(n, INF);
32     vector<int> parentF(n, -1), parentB(n, -1);
33     vector<char> visF(n, 0), visB(n, 0);
34     queue<int> qF, qB;
35 
36     // Initialize both sides
37     distF[s] = 0; visF[s] = 1; qF.push(s);
38     distB[t] = 0; visB[t] = 1; qB.push(t);
39 
40     auto reconstruct = [&](int meet) {
41         // Build path s -> meet using parentF
42         vector<int> left;
43         for (int v = meet; v != -1; v = parentF[v]) left.push_back(v);
44         reverse(left.begin(), left.end()); // s ... meet
45         // Build path meet -> t using parentB (following parents toward t)
46         vector<int> right;
47         for (int v = parentB[meet]; v != -1; v = parentB[v]) right.push_back(v);
48         // Combine
49         vector<int> path = left;
50         for (int v : right) path.push_back(v);
51         return path;
52     };
53 
54     auto expandLayer = [&](bool forward) -> int {
55         // Expand exactly one full BFS layer from the chosen side.
56         if (forward) {
57             int sz = (int)qF.size();
58             while (sz--) {
59                 int u = qF.front(); qF.pop();
60                 for (int v : g[u]) {
61                     if (!visF[v]) {
62                         visF[v] = 1;
63                         distF[v] = distF[u] + 1;
64                         parentF[v] = u;
65                         qF.push(v);
66                         if (visB[v]) return v; // Found meeting node
67                     }
68                 }
69             }
70         } else {
71             int sz = (int)qB.size();
72             while (sz--) {
73                 int u = qB.front(); qB.pop();
74                 for (int v : g[u]) {
75                     if (!visB[v]) {
76                         visB[v] = 1;
77                         distB[v] = distB[u] + 1;
78                         parentB[v] = u; // parent toward t in backward search
79                         qB.push(v);
80                         if (visF[v]) return v; // Found meeting node
81                     }
82                 }
83             }
84         }
85         return -1; // No meeting this layer
86     };
87 
88     int meet = -1;
89     while (!qF.empty() && !qB.empty() && meet == -1) {
90         // Heuristic: expand the smaller frontier to reduce work
91         bool forward = qF.size() <= qB.size();
92         meet = expandLayer(forward);
93     }
94 
95     if (meet == -1) {
96         cout << -1 << "\n"; // No path
97         return 0;
98     }
99 
100     vector<int> path = reconstruct(meet);
101     cout << (int)path.size() - 1 << "\n"; // distance in edges
102     for (int i = 0; i < (int)path.size(); ++i) {
103         cout << (path[i] + 1) << (i + 1 == (int)path.size() ? '\n' : ' ');
104     }
105     return 0;
106 }
107

This program performs bidirectional BFS on an undirected, unweighted graph. It maintains separate queues, visited flags, distances, and parents for forward (from s) and backward (from t) searches. Each iteration expands a full layer from the side with the smaller frontier, ensuring level-by-level correctness. As soon as a newly discovered node is already visited by the opposite search, a meeting node is found and the shortest path is reconstructed by concatenating the partial paths from s to meet and from meet to t.

Time: O(n + m)Space: O(n + m) for the graph; O(n) for distances, parents, and visited arrays; frontier size typically O(b^{d/2}).

Bidirectional Dijkstra on a directed graph with non-negative weights

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Bidirectional Dijkstra for directed graphs with non-negative weights.
5 // Reads: n m, m edges (u v w) 1-indexed, then s t (1-indexed). Builds reverse graph for backward search.
6 // Outputs: shortest distance and one shortest path (or -1 if none).
7 
8 using ll = long long;
9 const ll INFLL = (1LL<<62);
10 
11 struct Edge { int to; int w; };
12 
13 int main(){
14     ios::sync_with_stdio(false);
15     cin.tie(nullptr);
16 
17     int n, m; if(!(cin >> n >> m)) return 0;
18     vector<vector<Edge>> g(n), gr(n); // forward and reverse graphs
19     for(int i=0;i<m;++i){
20         int u,v,w; cin >> u >> v >> w; --u; --v;
21         g[u].push_back({v,w});
22         gr[v].push_back({u,w}); // reverse edge for backward search
23     }
24     int s,t; cin >> s >> t; --s; --t;
25     if(s==t){ cout << 0 << "\n" << (s+1) << "\n"; return 0; }
26 
27     vector<ll> distF(n, INFLL), distB(n, INFLL);
28     vector<int> parF(n, -1), parB(n, -1);
29     vector<char> usedF(n, 0), usedB(n, 0); // settled flags
30 
31     // Min-heaps of (dist, node)
32     using P = pair<ll,int>;
33     priority_queue<P, vector<P>, greater<P>> pqF, pqB;
34 
35     distF[s]=0; pqF.push({0,s});
36     distB[t]=0; pqB.push({0,t});
37 
38     ll best = INFLL; // best meeting distance found so far
39     int meet = -1;   // meeting node achieving best
40 
41     auto relax = [](ll &oldv, ll cand){ if(cand < oldv) oldv = cand; };
42 
43     auto tryImproveBest = [&](int u){
44         // If u is settled (or at least reached) in both sides, try to improve best
45         if(distF[u] < INFLL && distB[u] < INFLL){
46             if(distF[u] + distB[u] < best){ best = distF[u] + distB[u]; meet = u; }
47         }
48     };
49 
50     while(!pqF.empty() || !pqB.empty()){
51         ll topF = pqF.empty() ? INFLL : pqF.top().first;
52         ll topB = pqB.empty() ? INFLL : pqB.top().first;
53 
54         // Termination test: cannot beat current best
55         if(topF + topB >= best) break;
56 
57         if(topF <= topB){
58             // Expand one forward node
59             auto [du,u] = pqF.top(); pqF.pop();
60             if(usedF[u]) continue; // already settled
61             if(du != distF[u]) continue; // stale
62             usedF[u] = 1;
63             tryImproveBest(u);
64             for(const auto &e : g[u]){
65                 int v = e.to; ll nd = du + e.w;
66                 if(nd < distF[v]){
67                     distF[v] = nd; parF[v] = u; pqF.push({nd,v});
68                 }
69                 // Optional early best update via boundary nodes
70                 if(usedB[v]){ // v already settled backward; try meet at v
71                     if(distF[v] + distB[v] < best){ best = distF[v] + distB[v]; meet = v; }
72                 }
73             }
74         } else {
75             // Expand one backward node on reverse graph
76             auto [dv,u] = pqB.top(); pqB.pop();
77             if(usedB[u]) continue; // already settled
78             if(dv != distB[u]) continue; // stale
79             usedB[u] = 1;
80             tryImproveBest(u);
81             for(const auto &e : gr[u]){
82                 int v = e.to; ll nd = dv + e.w;
83                 if(nd < distB[v]){
84                     distB[v] = nd; parB[v] = u; pqB.push({nd,v});
85                 }
86                 if(usedF[v]){ // v already settled forward; try meet at v
87                     if(distF[v] + distB[v] < best){ best = distF[v] + distB[v]; meet = v; }
88                 }
89             }
90         }
91     }
92 
93     if(best >= INFLL){ cout << -1 << "\n"; return 0; }
94 
95     // Reconstruct path: s -> meet via parF, then meet -> t using parB (which follows reverse graph parents toward t)
96     vector<int> left;
97     for(int v = meet; v != -1; v = parF[v]) left.push_back(v);
98     reverse(left.begin(), left.end()); // s ... meet
99     vector<int> right;
100     for(int v = parB[meet]; v != -1; v = parB[v]) right.push_back(v);
101     vector<int> path = left; path.insert(path.end(), right.begin(), right.end());
102 
103     cout << best << "\n";
104     for(size_t i=0;i<path.size();++i){ cout << (path[i]+1) << (i+1==path.size()?'\n':' '); }
105     return 0;
106 }
107

This program implements bidirectional Dijkstra on a directed graph with non-negative weights. It runs Dijkstra from s on the original graph and from t on the reverse graph. It keeps the current best meeting distance best = min_v(distF[v] + distB[v]) and stops when minKey(pqF) + minKey(pqB) >= best, which ensures optimality. Parents are stored separately in each direction, allowing reconstruction of an s192t path via the meeting node.

Time: O((n + m) log n) using binary heapsSpace: O(n + m) for graphs plus O(n) for distances, parents, flags, and heap contents

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Bidirectional BFS for unweighted, undirected graphs.
5	// Reads: n m, then m edges (1-indexed or 0-indexed; we convert to 0-indexed here if needed), then s t (1-indexed).
6	// Outputs: shortest distance and one shortest path.
7
8	static const int INF = 1e9;
9
10	int main() {
11	ios::sync_with_stdio(false);
12	cin.tie(nullptr);
13
14	int n, m;
15	if (!(cin >> n >> m)) return 0;
16	vector<vector<int>> g(n);
17	for (int i = 0; i < m; ++i) {
18	int u, v; cin >> u >> v;
19	// Assume input is 1-indexed; convert to 0-indexed
20	--u; --v;
21	g[u].push_back(v);
22	g[v].push_back(u);
23	}
24	int s, t; cin >> s >> t; --s; --t;
25
26	if (s == t) {
27	cout << 0 << "\n" << (s+1) << "\n";
28	return 0;
29	}
30
31	vector<int> distF(n, INF), distB(n, INF);
32	vector<int> parentF(n, -1), parentB(n, -1);
33	vector<char> visF(n, 0), visB(n, 0);
34	queue<int> qF, qB;
35
36	// Initialize both sides
37	distF[s] = 0; visF[s] = 1; qF.push(s);
38	distB[t] = 0; visB[t] = 1; qB.push(t);
39
40	auto reconstruct = [&](int meet) {
41	// Build path s -> meet using parentF
42	vector<int> left;
43	for (int v = meet; v != -1; v = parentF[v]) left.push_back(v);
44	reverse(left.begin(), left.end()); // s ... meet
45	// Build path meet -> t using parentB (following parents toward t)
46	vector<int> right;
47	for (int v = parentB[meet]; v != -1; v = parentB[v]) right.push_back(v);
48	// Combine
49	vector<int> path = left;
50	for (int v : right) path.push_back(v);
51	return path;
52	};
53
54	auto expandLayer = [&](bool forward) -> int {
55	// Expand exactly one full BFS layer from the chosen side.
56	if (forward) {
57	int sz = (int)qF.size();
58	while (sz--) {
59	int u = qF.front(); qF.pop();
60	for (int v : g[u]) {
61	if (!visF[v]) {
62	visF[v] = 1;
63	distF[v] = distF[u] + 1;
64	parentF[v] = u;
65	qF.push(v);
66	if (visB[v]) return v; // Found meeting node
67	}
68	}
69	}
70	} else {
71	int sz = (int)qB.size();
72	while (sz--) {
73	int u = qB.front(); qB.pop();
74	for (int v : g[u]) {
75	if (!visB[v]) {
76	visB[v] = 1;
77	distB[v] = distB[u] + 1;
78	parentB[v] = u; // parent toward t in backward search
79	qB.push(v);
80	if (visF[v]) return v; // Found meeting node
81	}
82	}
83	}
84	}
85	return -1; // No meeting this layer
86	};
87
88	int meet = -1;
89	while (!qF.empty() && !qB.empty() && meet == -1) {
90	// Heuristic: expand the smaller frontier to reduce work
91	bool forward = qF.size() <= qB.size();
92	meet = expandLayer(forward);
93	}
94
95	if (meet == -1) {
96	cout << -1 << "\n"; // No path
97	return 0;
98	}
99
100	vector<int> path = reconstruct(meet);
101	cout << (int)path.size() - 1 << "\n"; // distance in edges
102	for (int i = 0; i < (int)path.size(); ++i) {
103	cout << (path[i] + 1) << (i + 1 == (int)path.size() ? '\n' : ' ');
104	}
105	return 0;
106	}
107

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Bidirectional Dijkstra for directed graphs with non-negative weights.
5	// Reads: n m, m edges (u v w) 1-indexed, then s t (1-indexed). Builds reverse graph for backward search.
6	// Outputs: shortest distance and one shortest path (or -1 if none).
7
8	using ll = long long;
9	const ll INFLL = (1LL<<62);
10
11	struct Edge { int to; int w; };
12
13	int main(){
14	ios::sync_with_stdio(false);
15	cin.tie(nullptr);
16
17	int n, m; if(!(cin >> n >> m)) return 0;
18	vector<vector<Edge>> g(n), gr(n); // forward and reverse graphs
19	for(int i=0;i<m;++i){
20	int u,v,w; cin >> u >> v >> w; --u; --v;
21	g[u].push_back({v,w});
22	gr[v].push_back({u,w}); // reverse edge for backward search
23	}
24	int s,t; cin >> s >> t; --s; --t;
25	if(s==t){ cout << 0 << "\n" << (s+1) << "\n"; return 0; }
26
27	vector<ll> distF(n, INFLL), distB(n, INFLL);
28	vector<int> parF(n, -1), parB(n, -1);
29	vector<char> usedF(n, 0), usedB(n, 0); // settled flags
30
31	// Min-heaps of (dist, node)
32	using P = pair<ll,int>;
33	priority_queue<P, vector<P>, greater<P>> pqF, pqB;
34
35	distF[s]=0; pqF.push({0,s});
36	distB[t]=0; pqB.push({0,t});
37
38	ll best = INFLL; // best meeting distance found so far
39	int meet = -1; // meeting node achieving best
40
41	auto relax = [](ll &oldv, ll cand){ if(cand < oldv) oldv = cand; };
42
43	auto tryImproveBest = [&](int u){
44	// If u is settled (or at least reached) in both sides, try to improve best
45	if(distF[u] < INFLL && distB[u] < INFLL){
46	if(distF[u] + distB[u] < best){ best = distF[u] + distB[u]; meet = u; }
47	}
48	};
49
50	while(!pqF.empty() \|\| !pqB.empty()){
51	ll topF = pqF.empty() ? INFLL : pqF.top().first;
52	ll topB = pqB.empty() ? INFLL : pqB.top().first;
53
54	// Termination test: cannot beat current best
55	if(topF + topB >= best) break;
56
57	if(topF <= topB){
58	// Expand one forward node
59	auto [du,u] = pqF.top(); pqF.pop();
60	if(usedF[u]) continue; // already settled
61	if(du != distF[u]) continue; // stale
62	usedF[u] = 1;
63	tryImproveBest(u);
64	for(const auto &e : g[u]){
65	int v = e.to; ll nd = du + e.w;
66	if(nd < distF[v]){
67	distF[v] = nd; parF[v] = u; pqF.push({nd,v});
68	}
69	// Optional early best update via boundary nodes
70	if(usedB[v]){ // v already settled backward; try meet at v
71	if(distF[v] + distB[v] < best){ best = distF[v] + distB[v]; meet = v; }
72	}
73	}
74	} else {
75	// Expand one backward node on reverse graph
76	auto [dv,u] = pqB.top(); pqB.pop();
77	if(usedB[u]) continue; // already settled
78	if(dv != distB[u]) continue; // stale
79	usedB[u] = 1;
80	tryImproveBest(u);
81	for(const auto &e : gr[u]){
82	int v = e.to; ll nd = dv + e.w;
83	if(nd < distB[v]){
84	distB[v] = nd; parB[v] = u; pqB.push({nd,v});
85	}
86	if(usedF[v]){ // v already settled forward; try meet at v
87	if(distF[v] + distB[v] < best){ best = distF[v] + distB[v]; meet = v; }
88	}
89	}
90	}
91	}
92
93	if(best >= INFLL){ cout << -1 << "\n"; return 0; }
94
95	// Reconstruct path: s -> meet via parF, then meet -> t using parB (which follows reverse graph parents toward t)
96	vector<int> left;
97	for(int v = meet; v != -1; v = parF[v]) left.push_back(v);
98	reverse(left.begin(), left.end()); // s ... meet
99	vector<int> right;
100	for(int v = parB[meet]; v != -1; v = parB[v]) right.push_back(v);
101	vector<int> path = left; path.insert(path.end(), right.begin(), right.end());
102
103	cout << best << "\n";
104	for(size_t i=0;i<path.size();++i){ cout << (path[i]+1) << (i+1==path.size()?'\n':' '); }
105	return 0;
106	}
107