I hate系しばしば遭遇するな。
https://yukicoder.me/problems/no/1612
問題
N頂点の連結無向グラフが与えられる。
各辺には1つ文字が設定されている。
1番の頂点からN番の頂点まで辺をたどって移動する際、経由した辺の文字を順に並べたものが回文でないようにしたい。
2N-1回以下の移動で条件を満たすものを示せ。
解法
全辺同じ文字の場合、どうやっても回文になるので解なし。
そうでない場合、2種類以上の文字を含む経路を求めよう。
これはBFSしたのち復元すればよい。
その結果が回文の場合、無駄に始点か終点の周りを適当に1往復する経路を追加すると回文ではなくなる。
int N,M; int C[201010]; vector<pair<int,int>> E[101010]; int from[101010][27]; int from2[101010][27]; void solve() { int i,j,k,l,r,x,y; string s; MINUS(from); cin>>N>>M; FOR(i,M) { cin>>x>>y>>s; E[x-1].push_back({y-1,i}); E[y-1].push_back({x-1,i}); C[i]=s[0]-'a'; } queue<int> Q; FORR2(e,x,E[0]) { from[e][C[x]]=-2; from2[e][C[x]]=x; Q.push(e*100+C[x]); } while(Q.size()) { int cur=Q.front()/100; int c=Q.front()%100; Q.pop(); FORR2(e,x,E[cur]) { if(c==26||c!=C[x]) { if(from[e][26]==-1) { from[e][26]=cur*100+c; from2[e][26]=x; Q.push(e*100+26); } } else { if(from[e][c]==-1) { from[e][c]=cur*100+c; from2[e][c]=x; Q.push(e*100+c); } } } } if(from[N-1][26]>=0) { vector<int> V; int cur=N-1; int c=26; while(cur!=0||c!=0) { V.push_back(from2[cur][c]); x=from[cur][c]; if(x==-2) break; cur=x/100; c=x%100; } V.push_back(E[0][0].second); V.push_back(E[0][0].second); reverse(ALL(V)); cout<<V.size()<<endl; FORR(v,V) cout<<(v+1)<<endl; return; } cout<<-1<<endl; }
まとめ
★3としては手ごろな問題。