算法
(BFS) $O(m^2)$
可以先考虑存图,对于每个点要存的信息是当前这个点的下一个点以及这两点之间的边权
由于题目给的图都是连通图,点 $1$ 和 $N$ 都至少有一条边与之相连,可以考虑按照当前点对应的边权是否相同这个规则从这两个点向下遍历从而构造回文,直到两个指针碰到一起的时候或者位于同一条边的两点时结束。
可能需要遍历的边的规模大概是 $O(\sum_a\sum_b deg(a)*deg(b)) = O(m^2)$,所以可以考虑使用 BFS
dp[a][b]
: 终点是 $a$ 和 $b$ 的回文串需要的费用
dp[i][i]
:回文串为偶数的费用
dp[i][e.to]
: 回文串为奇数的费用
然后遍历所有的情况找最小费用即可。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::vector;
using std::queue;
using P = std::pair<int, int>;
struct Edge {
int to, c;
Edge(int to, int c): to(to), c(c) {}
};
int main() {
int n, m;
cin >> n >> m;
vector<vector<Edge>> g(n);
rep(i, m) {
int a, b; char c;
cin >> a >> b >> c;
--a; --b;
g[a].emplace_back(b, c - 'a');
g[b].emplace_back(a, c - 'a');
}
const int INF = 1001001001;
vector<vector<int>> dp(n, vector<int>(n, INF));
queue<P> q;
auto push = [&](int a, int b, int x) {
if (dp[a][b] != INF) return;
dp[a][b] = x;
q.emplace(a, b);
};
push(0, n - 1, 0);
while (!q.empty()) {
auto [a, b] = q.front(); q.pop();
for (auto ea : g[a]) for (auto eb : g[b]) {
if (ea.c != eb.c) continue;
push(ea.to, eb.to, dp[a][b] + 1);
}
}
int ans = INF;
rep(i, n) {
ans = min(ans, dp[i][i] * 2);
for (auto e : g[i]) {
ans = min(ans, dp[i][e.to] * 2 + 1);
}
}
if (ans == INF) ans = -1;
cout << ans << '\n';
return 0;
}