Hello Codeforces community!↵
↵
We all know and love Breadth-First Search (BFS). It's our go-to for finding the shortest path in unweighted graphs. But what happens when the problem isn't just about moving a single entity from point A to point B? What if there are two entities moving simultaneously, or if the "state" of our problem involves more than just a single vertex?↵
↵
This is where the powerful technique of **BFS on a State-Space Graph (often implicitly a Product Graph)** comes into play. It's not a new algorithm, but rather a fundamental *application pattern* of BFS that allows us to tackle a much wider range of problems.↵
↵
---↵
↵
### The Core Concept: State-Space BFS↵
↵
Imagine your problem isn't just about a single node in a graph. Instead, the "situation" or "configuration" of your problem is more complex.↵
↵
* **What is a "State"?**↵
In State-Space BFS, a "state" is a tuple that encapsulates *all the necessary information* to describe the current configuration of your problem. This could be:↵
* `(position_of_agent_1, position_of_agent_2)`↵
* `(current_vertex, collected_items_mask)`↵
* `(current_vertex, remaining_fuel)`↵
* `(current_vertex, parity_of_path_length)`↵
* ...and many more!↵
↵
* **What are "Transitions" (Edges)?**↵
An edge in this conceptual state-space graph represents a valid "move" or "action" that transforms one state into another. These transitions often have a uniform "cost" (e.g., 1 unit of time, 1 step), making BFS suitable.↵
↵
* **The Implicit Graph:**↵
The crucial point is that we usually **do not explicitly build this massive state-space graph** in memory. If our original graph has $N$ vertices, and our state is `(pos_1, pos_2)`, the state-space graph can have $N \times N = N^2$ nodes! Building it explicitly would be too slow and memory-intensive.↵
↵
Instead, we perform BFS on this graph *implicitly*. We define our `dist` array (and queue) using the components of our state (e.g., `dist[pos_1][pos_2]`). When processing a state, we dynamically figure out its valid "neighbors" in the state space based on the problem's rules and the original graph's edges.↵
↵
* **Why BFS?**↵
Just like standard BFS, we use it because we're looking for the *minimum* number of steps (or minimum cost, if each transition costs 1) to reach a goal state. BFS's layer-by-layer exploration naturally finds the shortest path. It also handles cycles correctly by keeping track of visited states, ensuring optimality.↵
↵
---↵
↵
### Problem Example: AtCoder ABC197 F — Construct a Palindrome↵
↵
Let's illustrate this with a concrete example: [AtCoder ABC197 F — Construct a Palindrome](https://atcoder.jp/contests/abc197/tasks/abc197_f).↵
↵
**Problem Summary:**↵
You're given a connected, undirected graph with $N$ vertices and $M$ edges. Each edge has a character written on it. You need to find a path from Vertex 1 to Vertex N. If the string formed by concatenating the characters on the edges of this path can be a palindrome, find the *minimum possible length* of such a palindrome. Repetitions of vertices and edges are allowed. If no such palindrome can be formed, output -1.↵
↵
**Constraints:**↵
* $2 \le N \le 1000$↵
* $1 \le M \le 1000$↵
* Characters are lowercase English letters.↵
* Graph is connected.↵
↵
---↵
↵
### Initial Thoughts & Why Simple BFS Fails↵
↵
A naive BFS from Vertex 1 to Vertex N would find the shortest path in terms of the number of edges. However, this path doesn't guarantee a palindrome. For example, a path `1 --a--> 2 --b--> N` might be the shortest in terms of edges (length 2), but "ab" is not a palindrome. We need to consider the characters and the palindrome property, which simple BFS cannot do directly.↵
↵
---↵
↵
### The Core Idea: Two Travelers & State Definition↵
↵
To construct a palindrome string from a path `1 -> ... -> N`, we use a clever analogy: imagine **two "travelers" moving simultaneously** on the original graph.↵
↵
1. **Forward Traveler:** Starts at Vertex 1. As this traveler moves along an edge, the character on that edge forms the *next character in the first half* of our palindrome string.↵
2. **Backward Traveler:** Starts at Vertex N. As this traveler moves along an edge, the character on that edge forms the *next character in the second half* of our palindrome string, but it's effectively building the string *in reverse*.↵
↵
**The Palindrome Condition:** For the combined string to be a palindrome, at every "paired step" (when both travelers move one edge simultaneously), the character chosen by the forward traveler **must exactly match** the character chosen by the backward traveler.↵
↵
**Defining the State for BFS:**↵
Based on this "two travelers" idea, a state in our BFS needs to capture the positions of both travelers.↵
Our state will be a pair `(u, v)`, where:↵
* `u`: The current vertex of the **forward traveler** (who started at 1).↵
* `v`: The current vertex of the **backward traveler** (who started at N).↵
↵
We will use `dist[u][v]` to store the minimum number of "paired steps" (simultaneous moves by both travelers) it takes to reach the state `(u, v)`.↵
↵
---↵
↵
### BFS Algorithm Details↵
↵
1. **Initialization:**↵
* We use a 2D array `dist[N+1][N+1]`, initialized to -1 (or a large value like `INF`) to mark all states `(u, v)` as unvisited.↵
* Our BFS queue will store pairs of integers: `queue<pair<int, int>> q;`.↵
* The **starting state** for the BFS is `(1, N)`. This is where our two travelers begin.↵
* Set `dist[1][N] = 0` (0 paired steps taken initially).↵
* Add `(1, N)` to the BFS queue: `q.push({1, N});`.↵
↵
2. **Transitions (Exploring Next States):**↵
When we dequeue a state `(u, v)` with `d = dist[u][v]` (meaning `d` paired steps have been taken so far):↵
↵
* We iterate through every possible edge `(u, next_u)` with character `char_A` that the forward traveler can take from `u`.↵
* Simultaneously, we iterate through every possible edge `(v, next_v)` with character `char_B` that the backward traveler can take from `v`.↵
↵
* **The Crucial Condition:** For the combined string to be a palindrome, the characters chosen by both travelers in this paired step **must match**: `char_A == char_B`.↵
* If `char_A == char_B`:↵
* This forms a valid next combined state `(next_u, next_v)`.↵
* If `(next_u, next_v)` has not been visited (`dist[next_u][next_v] == -1`):↵
* Set `dist[next_u][next_v] = d + 1` (one more paired step).↵
* Enqueue `(next_u, next_v)`.↵
* **Why `dist[next_u][next_v] == -1`?** This is fundamental to BFS for shortest paths. If a state has already been visited, it means we've found an equally short or shorter path to it already. Re-visiting it won't lead to a shorter overall palindrome. This also prevents infinite loops in cycles.↵
↵
3. **Finding the Answer (Minimum Palindrome Length):**↵
The `d = dist[u][v]` value represents the number of paired steps. Each paired step adds two characters to the palindrome (one to the front, one to the back). The total palindrome length depends on how the travelers "meet":↵
↵
* **Case 1: Even Length Palindrome (Travelers meet at the same vertex)**↵
If, at any point, the forward traveler reaches vertex `u` and the backward traveler also reaches the *same* vertex `u` (i.e., `u == v`), they have successfully met. The palindrome string is formed by `(first d characters) + (reversed last d characters)`.↵
* Total length: `2 * d`.↵
* We update `min_palindrome_length = min(min_palindrome_length, 2 * d)`.↵
↵
* **Case 2: Odd Length Palindrome (Travelers meet on an edge)**↵
If, at any point, the forward traveler is at `u` and the backward traveler is at `v`, AND there is a direct edge between `u` and `v` in the original graph (with *any* character `c`), this edge can serve as the single "middle" character of the palindrome.↵
* Total length: `2 * d + 1`.↵
* We update `min_palindrome_length = min(min_palindrome_length, 2 * d + 1)`.↵
↵
We maintain a `min_palindrome_length` variable (initialized to `INF`) and update it with the minimum value found from these two cases whenever we dequeue a state `(u, v)`. Because BFS explores layer by layer, the first time we find a path to a certain `d`, it's the minimum `d` for that state. Thus, the overall `min_palindrome_length` will be the absolute minimum.↵
↵
4. **Optimization (Pruning):**↵
Inside the BFS loop, before exploring `(next_u, next_v)` from `(u, v)`, we can add an optimization:↵
`if (d * 2 >= min_palindrome_length && (d * 2 + 1) >= min_palindrome_length) continue;`↵
This means if the current number of paired steps `d` already implies that any palindrome formed by extending from this state will be longer than or equal to the best palindrome found so far, we can stop exploring further from this state. This significantly prunes the search space.↵
↵
5. **Final Output:**↵
After the BFS completes, if `min_palindrome_length` is still `INF`, it means no palindrome path was found. Output -1. Otherwise, output `min_palindrome_length`.↵
↵
---↵
↵
### Complexity Analysis↵
↵
* **Time Complexity:** $O(N^2 + M^2)$↵
* There are $N \times N = N^2$ possible states `(u, v)`. Each state is visited at most once.↵
* From each state `(u, v)`, we iterate through `deg(u)` edges for the forward traveler and `deg(v)` edges for the backward traveler. The total number of pairs of edges is `deg(u) * deg(v)`.↵
* Summing this over all possible states, the total transitions are bounded by $M \times M = M^2$.↵
* Given $N, M \le 1000$: $N^2 = 10^6$, $M^2 = 10^6$. The total operations are roughly $10^6 + 10^6 = 2 \times 10^6$, which is very efficient and passes within the 3-second time limit.↵
↵
* **Space Complexity:** $O(N^2 + M)$↵
* $O(N^2)$ for the `dist` array (e.g., `dist[1001][1001]` integers). For $N=1000$, this is about 4 MB, well within the 1024 MiB memory limit.↵
* $O(N+M)$ for the adjacency list.↵
↵
---↵
↵
### General Takeaways: When to Use State-Space BFS↵
↵
This powerful technique is applicable in many competitive programming scenarios:↵
↵
1. **Multiple Interacting Agents/Entities:** When your problem involves two or more entities moving or interacting in a graph, and their actions are coupled (e.g., they move simultaneously, or one's move affects the other).↵
2. **Complex States (More than just a single vertex):** When the "state" of your problem requires more information than just a single vertex ID. This extra information becomes part of your state tuple (e.g., `(current_vertex, bitmask_of_collected_items)`, `(current_vertex, remaining_fuel)`).↵
3. **Shortest Path on an Implicit Graph:** When you need to find the minimum number of steps/cost, but the graph you're searching on isn't explicitly given; instead, its nodes and edges are derived from a simpler base graph and problem rules. This is particularly effective for unweighted graphs (where each "step" in the state space costs 1). If costs vary, Dijkstra's algorithm would be used on the state-space graph instead of BFS.↵
4. **Handling Cycles in DP-like Problems:** While Dynamic Programming usually applies to Directed Acyclic Graphs (DAGs), problems that look like DP but have cycles in their state dependencies can often be solved with BFS/Dijkstra's on the state-space graph. BFS naturally handles cycles by tracking visited states.↵
↵
By understanding how to define your problem's "state" and "transitions," you can transform seemingly complex problems into standard graph search problems on a larger, implicit state space.↵
↵
---↵
↵
### C++ Code Implementation↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
↵
const int INF = 1e9 + 7;↵
const int MAXN = 1001;↵
↵
struct Edge {↵
int to;↵
char character;↵
};↵
vector<vector<Edge>> adj(MAXN);↵
int dist[MAXN][MAXN];↵
↵
int bfs(int N,int M){↵
memset(dist, -1, sizeof(dist));↵
queue<pair<int, int>> q;↵
dist[1][N]=0;↵
q.push({1, N});↵
↵
int min_pall_length = INF;↵
while (!q.empty()) {↵
pair<int,int> curr= q.front();↵
q.pop();↵
int u = curr.first;↵
int v = curr.second;↵
int d = dist[u][v];↵
↵
// -- Checking the current state if it can form a pallindrome or final answer --↵
// Candidate 1: Even length palindrome.↵
if(u==v) {↵
min_pall_length = min(min_pall_length, 2*d);↵
}↵
// Candidate 2: Odd length palindrome.↵
for(const Edge &edge:adj[u]){↵
if(edge.to==v) min_pall_length = min(min_pall_length, 2 * d + 1);↵
}↵
// pruning: If the current distance is already greater than the minimum found, skip further processing.↵
// Skip further expansion from this state and move to the next in the queue.↵
if (d * 2 >= min_pall_length && (d * 2 + 1) >= min_pall_length) {↵
continue; ↵
}↵
↵
// -- Expanding the BFS from the current state --↵
for( auto edge:adj[u]){↵
int next_u=edge.to;↵
char char_a= edge.character;↵
↵
for(auto edgev:adj[v]){↵
int next_v=edgev.to;↵
char char_b=edgev.character;↵
↵
// condition for pallindrome formation↵
if(char_a==char_b){↵
if(dist[next_u][next_v]==-1 || dist[next_u][next_v]>d+1){↵
dist[next_u][next_v] = d + 1;↵
q.push({next_u, next_v});↵
}↵
}↵
}↵
}↵
↵
↵
}↵
return (min_pall_length == INF) ? -1 : min_pall_length;↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
int N, M; // N: number of vertices, M: number of edges↵
cin >> N >> M;↵
↵
for (int i = 0; i < M; ++i) {↵
int u, v;↵
char c;↵
cin >> u >> v >> c;↵
adj[u].push_back({v, c});↵
adj[v].push_back({u, c}); // Add edge for the reverse direction↵
}↵
int result = bfs(N, M);↵
cout << result << endl;↵
return 0;↵
}`↵
~~~~~↵
↵
↵
We all know and love Breadth-First Search (BFS). It's our go-to for finding the shortest path in unweighted graphs. But what happens when the problem isn't just about moving a single entity from point A to point B? What if there are two entities moving simultaneously, or if the "state" of our problem involves more than just a single vertex?↵
↵
This is where the powerful technique of **BFS on a State-Space Graph (often implicitly a Product Graph)** comes into play. It's not a new algorithm, but rather a fundamental *application pattern* of BFS that allows us to tackle a much wider range of problems.↵
↵
---↵
↵
### The Core Concept: State-Space BFS↵
↵
Imagine your problem isn't just about a single node in a graph. Instead, the "situation" or "configuration" of your problem is more complex.↵
↵
* **What is a "State"?**↵
In State-Space BFS, a "state" is a tuple that encapsulates *all the necessary information* to describe the current configuration of your problem. This could be:↵
* `(position_of_agent_1, position_of_agent_2)`↵
* `(current_vertex, collected_items_mask)`↵
* `(current_vertex, remaining_fuel)`↵
* `(current_vertex, parity_of_path_length)`↵
* ...and many more!↵
↵
* **What are "Transitions" (Edges)?**↵
An edge in this conceptual state-space graph represents a valid "move" or "action" that transforms one state into another. These transitions often have a uniform "cost" (e.g., 1 unit of time, 1 step), making BFS suitable.↵
↵
* **The Implicit Graph:**↵
The crucial point is that we usually **do not explicitly build this massive state-space graph** in memory. If our original graph has $N$ vertices, and our state is `(pos_1, pos_2)`, the state-space graph can have $N \times N = N^2$ nodes! Building it explicitly would be too slow and memory-intensive.↵
↵
Instead, we perform BFS on this graph *implicitly*. We define our `dist` array (and queue) using the components of our state (e.g., `dist[pos_1][pos_2]`). When processing a state, we dynamically figure out its valid "neighbors" in the state space based on the problem's rules and the original graph's edges.↵
↵
* **Why BFS?**↵
Just like standard BFS, we use it because we're looking for the *minimum* number of steps (or minimum cost, if each transition costs 1) to reach a goal state. BFS's layer-by-layer exploration naturally finds the shortest path. It also handles cycles correctly by keeping track of visited states, ensuring optimality.↵
↵
---↵
↵
### Problem Example: AtCoder ABC197 F — Construct a Palindrome↵
↵
Let's illustrate this with a concrete example: [AtCoder ABC197 F — Construct a Palindrome](https://atcoder.jp/contests/abc197/tasks/abc197_f).↵
↵
**Problem Summary:**↵
You're given a connected, undirected graph with $N$ vertices and $M$ edges. Each edge has a character written on it. You need to find a path from Vertex 1 to Vertex N. If the string formed by concatenating the characters on the edges of this path can be a palindrome, find the *minimum possible length* of such a palindrome. Repetitions of vertices and edges are allowed. If no such palindrome can be formed, output -1.↵
↵
**Constraints:**↵
* $2 \le N \le 1000$↵
* $1 \le M \le 1000$↵
* Characters are lowercase English letters.↵
* Graph is connected.↵
↵
---↵
↵
### Initial Thoughts & Why Simple BFS Fails↵
↵
A naive BFS from Vertex 1 to Vertex N would find the shortest path in terms of the number of edges. However, this path doesn't guarantee a palindrome. For example, a path `1 --a--> 2 --b--> N` might be the shortest in terms of edges (length 2), but "ab" is not a palindrome. We need to consider the characters and the palindrome property, which simple BFS cannot do directly.↵
↵
---↵
↵
### The Core Idea: Two Travelers & State Definition↵
↵
To construct a palindrome string from a path `1 -> ... -> N`, we use a clever analogy: imagine **two "travelers" moving simultaneously** on the original graph.↵
↵
1. **Forward Traveler:** Starts at Vertex 1. As this traveler moves along an edge, the character on that edge forms the *next character in the first half* of our palindrome string.↵
2. **Backward Traveler:** Starts at Vertex N. As this traveler moves along an edge, the character on that edge forms the *next character in the second half* of our palindrome string, but it's effectively building the string *in reverse*.↵
↵
**The Palindrome Condition:** For the combined string to be a palindrome, at every "paired step" (when both travelers move one edge simultaneously), the character chosen by the forward traveler **must exactly match** the character chosen by the backward traveler.↵
↵
**Defining the State for BFS:**↵
Based on this "two travelers" idea, a state in our BFS needs to capture the positions of both travelers.↵
Our state will be a pair `(u, v)`, where:↵
* `u`: The current vertex of the **forward traveler** (who started at 1).↵
* `v`: The current vertex of the **backward traveler** (who started at N).↵
↵
We will use `dist[u][v]` to store the minimum number of "paired steps" (simultaneous moves by both travelers) it takes to reach the state `(u, v)`.↵
↵
---↵
↵
### BFS Algorithm Details↵
↵
1. **Initialization:**↵
* We use a 2D array `dist[N+1][N+1]`, initialized to -1 (or a large value like `INF`) to mark all states `(u, v)` as unvisited.↵
* Our BFS queue will store pairs of integers: `queue<pair<int, int>> q;`.↵
* The **starting state** for the BFS is `(1, N)`. This is where our two travelers begin.↵
* Set `dist[1][N] = 0` (0 paired steps taken initially).↵
* Add `(1, N)` to the BFS queue: `q.push({1, N});`.↵
↵
2. **Transitions (Exploring Next States):**↵
When we dequeue a state `(u, v)` with `d = dist[u][v]` (meaning `d` paired steps have been taken so far):↵
↵
* We iterate through every possible edge `(u, next_u)` with character `char_A` that the forward traveler can take from `u`.↵
* Simultaneously, we iterate through every possible edge `(v, next_v)` with character `char_B` that the backward traveler can take from `v`.↵
↵
* **The Crucial Condition:** For the combined string to be a palindrome, the characters chosen by both travelers in this paired step **must match**: `char_A == char_B`.↵
* If `char_A == char_B`:↵
* This forms a valid next combined state `(next_u, next_v)`.↵
* If `(next_u, next_v)` has not been visited (`dist[next_u][next_v] == -1`):↵
* Set `dist[next_u][next_v] = d + 1` (one more paired step).↵
* Enqueue `(next_u, next_v)`.↵
* **Why `dist[next_u][next_v] == -1`?** This is fundamental to BFS for shortest paths. If a state has already been visited, it means we've found an equally short or shorter path to it already. Re-visiting it won't lead to a shorter overall palindrome. This also prevents infinite loops in cycles.↵
↵
3. **Finding the Answer (Minimum Palindrome Length):**↵
The `d = dist[u][v]` value represents the number of paired steps. Each paired step adds two characters to the palindrome (one to the front, one to the back). The total palindrome length depends on how the travelers "meet":↵
↵
* **Case 1: Even Length Palindrome (Travelers meet at the same vertex)**↵
If, at any point, the forward traveler reaches vertex `u` and the backward traveler also reaches the *same* vertex `u` (i.e., `u == v`), they have successfully met. The palindrome string is formed by `(first d characters) + (reversed last d characters)`.↵
* Total length: `2 * d`.↵
* We update `min_palindrome_length = min(min_palindrome_length, 2 * d)`.↵
↵
* **Case 2: Odd Length Palindrome (Travelers meet on an edge)**↵
If, at any point, the forward traveler is at `u` and the backward traveler is at `v`, AND there is a direct edge between `u` and `v` in the original graph (with *any* character `c`), this edge can serve as the single "middle" character of the palindrome.↵
* Total length: `2 * d + 1`.↵
* We update `min_palindrome_length = min(min_palindrome_length, 2 * d + 1)`.↵
↵
We maintain a `min_palindrome_length` variable (initialized to `INF`) and update it with the minimum value found from these two cases whenever we dequeue a state `(u, v)`. Because BFS explores layer by layer, the first time we find a path to a certain `d`, it's the minimum `d` for that state. Thus, the overall `min_palindrome_length` will be the absolute minimum.↵
↵
4. **Optimization (Pruning):**↵
Inside the BFS loop, before exploring `(next_u, next_v)` from `(u, v)`, we can add an optimization:↵
`if (d * 2 >= min_palindrome_length && (d * 2 + 1) >= min_palindrome_length) continue;`↵
This means if the current number of paired steps `d` already implies that any palindrome formed by extending from this state will be longer than or equal to the best palindrome found so far, we can stop exploring further from this state. This significantly prunes the search space.↵
↵
5. **Final Output:**↵
After the BFS completes, if `min_palindrome_length` is still `INF`, it means no palindrome path was found. Output -1. Otherwise, output `min_palindrome_length`.↵
↵
---↵
↵
### Complexity Analysis↵
↵
* **Time Complexity:** $O(N^2 + M^2)$↵
* There are $N \times N = N^2$ possible states `(u, v)`. Each state is visited at most once.↵
* From each state `(u, v)`, we iterate through `deg(u)` edges for the forward traveler and `deg(v)` edges for the backward traveler. The total number of pairs of edges is `deg(u) * deg(v)`.↵
* Summing this over all possible states, the total transitions are bounded by $M \times M = M^2$.↵
* Given $N, M \le 1000$: $N^2 = 10^6$, $M^2 = 10^6$. The total operations are roughly $10^6 + 10^6 = 2 \times 10^6$, which is very efficient and passes within the 3-second time limit.↵
↵
* **Space Complexity:** $O(N^2 + M)$↵
* $O(N^2)$ for the `dist` array (e.g., `dist[1001][1001]` integers). For $N=1000$, this is about 4 MB, well within the 1024 MiB memory limit.↵
* $O(N+M)$ for the adjacency list.↵
↵
---↵
↵
### General Takeaways: When to Use State-Space BFS↵
↵
This powerful technique is applicable in many competitive programming scenarios:↵
↵
1. **Multiple Interacting Agents/Entities:** When your problem involves two or more entities moving or interacting in a graph, and their actions are coupled (e.g., they move simultaneously, or one's move affects the other).↵
2. **Complex States (More than just a single vertex):** When the "state" of your problem requires more information than just a single vertex ID. This extra information becomes part of your state tuple (e.g., `(current_vertex, bitmask_of_collected_items)`, `(current_vertex, remaining_fuel)`).↵
3. **Shortest Path on an Implicit Graph:** When you need to find the minimum number of steps/cost, but the graph you're searching on isn't explicitly given; instead, its nodes and edges are derived from a simpler base graph and problem rules. This is particularly effective for unweighted graphs (where each "step" in the state space costs 1). If costs vary, Dijkstra's algorithm would be used on the state-space graph instead of BFS.↵
4. **Handling Cycles in DP-like Problems:** While Dynamic Programming usually applies to Directed Acyclic Graphs (DAGs), problems that look like DP but have cycles in their state dependencies can often be solved with BFS/Dijkstra's on the state-space graph. BFS naturally handles cycles by tracking visited states.↵
↵
By understanding how to define your problem's "state" and "transitions," you can transform seemingly complex problems into standard graph search problems on a larger, implicit state space.↵
↵
---↵
↵
### C++ Code Implementation↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
↵
const int INF = 1e9 + 7;↵
const int MAXN = 1001;↵
↵
struct Edge {↵
int to;↵
char character;↵
};↵
vector<vector<Edge>> adj(MAXN);↵
int dist[MAXN][MAXN];↵
↵
int bfs(int N,int M){↵
memset(dist, -1, sizeof(dist));↵
queue<pair<int, int>> q;↵
dist[1][N]=0;↵
q.push({1, N});↵
↵
int min_pall_length = INF;↵
while (!q.empty()) {↵
pair<int,int> curr= q.front();↵
q.pop();↵
int u = curr.first;↵
int v = curr.second;↵
int d = dist[u][v];↵
↵
// -- Checking the current state if it can form a pallindrome or final answer --↵
// Candidate 1: Even length palindrome.↵
if(u==v) {↵
min_pall_length = min(min_pall_length, 2*d);↵
}↵
// Candidate 2: Odd length palindrome.↵
for(const Edge &edge:adj[u]){↵
if(edge.to==v) min_pall_length = min(min_pall_length, 2 * d + 1);↵
}↵
// pruning: If the current distance is already greater than the minimum found, skip further processing.↵
// Skip further expansion from this state and move to the next in the queue.↵
if (d * 2 >= min_pall_length && (d * 2 + 1) >= min_pall_length) {↵
continue; ↵
}↵
↵
// -- Expanding the BFS from the current state --↵
for( auto edge:adj[u]){↵
int next_u=edge.to;↵
char char_a= edge.character;↵
↵
for(auto edgev:adj[v]){↵
int next_v=edgev.to;↵
char char_b=edgev.character;↵
↵
// condition for pallindrome formation↵
if(char_a==char_b){↵
if(dist[next_u][next_v]==-1 || dist[next_u][next_v]>d+1){↵
dist[next_u][next_v] = d + 1;↵
q.push({next_u, next_v});↵
}↵
}↵
}↵
}↵
↵
↵
}↵
return (min_pall_length == INF) ? -1 : min_pall_length;↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
int N, M; // N: number of vertices, M: number of edges↵
cin >> N >> M;↵
↵
for (int i = 0; i < M; ++i) {↵
int u, v;↵
char c;↵
cin >> u >> v >> c;↵
adj[u].push_back({v, c});↵
adj[v].push_back({u, c}); // Add edge for the reverse direction↵
}↵
int result = bfs(N, M);↵
cout << result << endl;↵
return 0;↵
}`↵
~~~~~↵
↵
