ABC197F
問題文で与えられたグラフを \(G\) とおく．
解法1: BFS
素直な実装． 頂点が \(N \times N\) のグラフ \(\hat{G}\) を考える． \(\hat{G}\) における 頂点 \(\,(x,y), (nx,ny)\,\) に対する辺は， \(G\) において辺 \(e = (x,y,c), ne = (nx,ny,nc)\) が存在して \(c = nc\) のときに張る． ここで，\(e\)は \(x\) から \(y\) への辺であって，文字 \(c\) が割り当てられているものを表す．
\(\hat{G}\) における遷移は， 回文を外側から 2文字ずつ決めていることに対応する． 回文の長さが偶数か奇数かで場合分けして答えを求める． 奇数の場合は，真ん中に使われる辺 \(\,(x,y,c)\,\) を全探索． \(\,(y,x,c)\,\) も候補に入ることを忘れずに．
解法2: Dijikstra
大まかな流れは解法 1と同じ． 基本的には外側の 2文字ずつ決めていくので， \(\hat{G}\) にコスト 2の辺を張る． ただし，回文の真ん中に使える辺のみ，コスト 1の辺を張る． つまり，\(\,(x,y) \rightarrow (nx,ny)\,\) の遷移において， \(y = nx\) かつ \(x = ny\) のとき，\(G\) において同じ辺を使っている． そこで，この遷移を \(\,(x,y) \rightarrow (nx,nx)\,\) として， コストを 1とする．なお，真ん中の辺であるため \(\,(x,y)\,\) の色には依らない．
最後に答えを集計する． これらの実装により， 偶数長と奇数長の場合分けは済んでいるので， \(G\) において終わる頂点 \(i\) を全探索すればよい． つまり，\(\hat{G}\) において \(\,(i,i)\,\) を全探索すればよい．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
// BFS
int main() {
ll n,m;
cin >> n >> m;
rep(i,m){
ll a,b; char c; cin >> a >> b >> c;
--a, --b;
to[a].emplace_back(b,c);
to[b].emplace_back(a,c);
ed[i] = {a,b};
}
queue<pll> q;
vvll dis(n, vll(n, INFL));
auto push = [&](ll x, ll y, ll d) -> void {
if(dis[x][y] != INFL) return;
dis[x][y] = d;
q.push({x,y});
};
push(0,n-1, 0);
while(q.size()){
auto [x,y] = q.front(); q.pop();
for(auto [nx, nc]: to[x]) {
for(auto [ny, nd]: to[y]){
if(nc == nd){
push(nx, ny, dis[x][y]+1);
}
}
}
}
ll ans = INFL;
// 偶数長
rep(i,n){
chmin(ans, dis[i][i]*2);
}
// 奇数長のとき
// 最後に使う辺を全探索
for(auto [x,y]: ed){
// Remark : edge [x,y] に対して，[x][y], [y][x] の二種類あり得る．
chmin(ans, dis[x][y]*2 + 1);
chmin(ans, dis[y][x]*2 + 1);
}
if(ans >= INFL) ans = -1;
cout << ans << endl;
return 0;
}
// Dijikstra
int main() {
ll n,m;
cin >> n >> m;
rep(i,m){
ll a,b; char c; cin >> a >> b >> c;
--a, --b;
to[a].emplace_back(b,c);
to[b].emplace_back(a,c);
ed[i] = {a,b};
}
min_priority_queue<tuple<ll,ll,ll>> q;
vvll dis(n, vll(n, INFL));
auto push = [&](ll x, ll y, ll d) -> void {
if(chmin(dis[x][y], d)){ // push 関数の中で chmin は定数倍が重い
q.push({d,x,y});
}
};
push(0,n-1, 0);
while(q.size()){
auto [d,x,y] = q.top(); q.pop();
if(d != dis[x][y]) continue;
for(auto [nx, nc]: to[x]) {
for(auto [ny, nd]: to[y]){
if(nc == nd){
push(nx, ny, d+2); // 定数倍を軽くするなら，push 関数を呼ぶ前に chmin
}
// nc, nd に依らない
if(nx == y && ny == x){
ny = nx;
push(nx, ny, d+1);
}
}
}
}
ll ans = INFL;
rep(i,n) chmin(ans, dis[i][i]);
if(ans >= INFL) ans = -1;
cout << ans << endl;
return 0;
}
