Puoi leggere e provare a risolvere il problema palindromo
visitando la piattaforma Terry.
Hint 1. Immagina che Monica e Mojito camminino lungo il percorso in modo speculare.
Hint 2. Costruisci un opportuno "grafo ausiliario".
Hint 3. I nodi del grafo ausiliario sono coppie ordinate di incroci. E gli archi?
Hint 4. BFS sul grafo ausiliario.
Supponiamo di aver trovato un percorso palindromo di lunghezza minima. Sia esso
Immaginiamo ora che Monica inizi a camminare lungo questo percorso, partendo da . Ogni volta che percorre una strada, Mojito (che parte da ) percorre a sua volta una strada in senso opposto. In altre parole, quando Monica percorre la strada , Mojito percorre la strada .
Osserviamo che, ogni secondo, Monica e Mojito percorreranno sempre strade con la stessa lettera. Inoltre, ci sarà un momento in cui Monica e Mojito saranno o sullo stesso incrocio (se è dispari) o su due incroci direttamente collegati da una strada (se è pari).
L'idea è quindi quella di considerare un grafo ausiliario. I nodi di questo grafo sono costituiti da tutte le coppie ordinate di incroci. La coppia rappresenta la situazione in cui Monica si trova nell'incrocio e Mojito nell'incrocio .
Ora, dati due nodi e , quand'è che vi è un arco che li collega? La domanda è equivalente a: quand'è che Monica e Mojito sono autorizzati a spostarsi dalla coppia alla coppia ? La risposta è: quando esistono le strade e , e inoltre le lettere corrispondenti a tali due strade sono uguali.
Per costruire il grafo ausiliario, iteriamo su tutte le coppie (ordinate) di strade distinte. Se la prima strada della coppia è e la seconda , e se le lettere associate a tali strade sono uguali, aggiungiamo l'arco che collega a e quello che collega a .
Ora che abbiamo il grafo, calcoliamo le distanze di tutti i nodi del grafo dal nodo di partenza, che è . Ciò si fa agevolmente facendo partire una visita in ampiezza (BFS) da . Sia la distanza dal nodo . Se non è raggiungibile da , poniamo , dove, nella pratica, è un numero molto grande (ad esempio ).
Iteriamo poi su tutti i nodi tali che oppure esiste la strada . In particolare:
La risposta si ottiene dunque prendendo il minimo di queste quantità.
C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1e9;
struct Node {
int u, v;
Node(int _u, int _v): u(_u), v(_v) {}
};
struct Graph {
int n;
vector<vector<vector<Node>>> adj;
vector<vector<int>> dist;
Graph(int _n): n(_n) {
adj.assign(n, vector<vector<Node>>(n));
dist.assign(n, vector<int>(n, INF));
}
void add_edge(Node x, Node y) {
adj[x.u][x.v].push_back(y);
adj[y.u][y.v].push_back(x);
}
vector<Node> adj_list(Node x) {
return adj[x.u][x.v];
}
int get_dist(Node x) {
return dist[x.u][x.v];
}
void set_dist(Node x, int d) {
dist[x.u][x.v] = d;
}
};
void bfs(Node source, Graph& graph) {
queue<Node> Q;
graph.set_dist(source, 0);
Q.push(source);
while (!Q.empty()) {
Node x = Q.front();
Q.pop();
for (Node y : graph.adj_list(x)) {
if (graph.get_dist(y) != INF) continue;
graph.set_dist(y, graph.get_dist(x) + 1);
Q.push(y);
}
}
}
void solve(int t) {
int N, M, X, Y;
cin >> N >> M;
cin >> X >> Y;
vector<int> A(M), B(M);
vector<char> L(M);
for (int i = 0; i < M; i++)
cin >> A[i] >> B[i] >> L[i];
Graph graph(N);
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
if (L[i] != L[j]) continue;
graph.add_edge(Node(A[i], A[j]), Node(B[i], B[j]));
graph.add_edge(Node(A[i], B[j]), Node(B[i], A[j]));
}
}
bfs(Node(X, Y), graph);
int ans = INF;
for (int i = 0; i < N; i++)
ans = min(ans, 2 * graph.get_dist(Node(i, i)));
for (int i = 0; i < M; i++) {
ans = min(ans, 2 * graph.get_dist(Node(A[i], B[i])) + 1);
ans = min(ans, 2 * graph.get_dist(Node(B[i], A[i])) + 1);
}
cout << "Case #" << t << ": " << (ans == INF ? -1 : ans) << "\n";
}
int main() {
int T;
cin >> T;
for (int t = 1; t <= T; t++) solve(t);
return 0;
}