题解：AT_abc244_f [ABC244F] Shortest Good Path

fengpengyu · 2026-01-22 18:37:05 · 题解

考虑状态压缩。

可以设 dp_{i,u} 表示当前的 S 字符串状态为 i，且该路径终点为 u 的最小长度，对于一个点，多走一次就会让 i 相对应的第 u 位从偶数状态变成奇数状态，或从奇数状态变为偶数状态，也就是相当于取反操作。于是就有了 dp_{i,u}=dp_{i⊕2^v,v}+1 这一转移式子。考虑到是图上问题，所以使用 BFS 求值，每一次把新增入的状态加进队列里就行了。

初始化令 dp_{2^i,i}=1，其余设为正无穷。

放一下 BFS 的代码

while(!mine.empty()){
  int s=mine.front().first,x=mine.front().second;
  mine.pop();
  for(int i=head[x];i;i=E[i].nxt){
    int v=E[i].to,p=s^(1<<v);
    if(dp[p][v]!=res) continue;//res是正无穷
    dp[p][v]=dp[s][x]+1;
    mine.push({p,v});
  }
}