AGC010B Boxes
这道题其实是一道 01BFS 求最短路的模型，但是建模比较难想。
首先需要想到对于每个集合内的点两两连边，边权为 \(1\)，由于开始和结束时需要从起点到中转点和中转点到终点，而我们要求的其实是中转点的数量，如果我们直接求一遍最短路（这样的话用的是普通 bfs），中准点之间是 ans-1，加上起点终点，变为 ans+1，所以这样求出来结果要 \(-1\)。
其次，这样建图复杂度高达 \(O(\sum_{i=1}^n \dfrac{A_i(A_i-1)}{2})\)，不可取，考虑到一个套路的方法：虚拟结点。每个集合配备一个虚拟节点。即一个集合内的所有点先向该集合对应的虚拟节点连一条长度为 \(1\) 的，再反方向连长度为 \(0\) 的，这样就等价于两两连长为 \(1\) 的边。这样边数就降至 \(2\sum_{i=1}^nA_i^2\)，然后点数就是 \(n+m\)，复杂度就是点数与边数之和。
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define get(x) (x<0?x+=N:(x>=N?x-=N:1))
const int N=400010;
int n,m,q[N],dis[N];
vector<pair<int,bool>>g[N];
int main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
scanf("%d%d",&n,&m);
int ttt=0;
E(i, n){
int tot;
scanf("%d",&tot);
W(tot){
int x;
scanf("%d",&x);
g[x].emplace_back(m+i,1);
g[m+i].emplace_back(x,0);
ttt+=2;
// printf("%d %d %d\n%d %d %d\n",x,m+i,1,m+i,x,0);
}
}
// printf("%d",ttt);
memset(dis+2,0x3f,(m+n-1)*4);
int hh=0,tt=0;
q[tt++]=1;
while(hh!=tt){
int u=q[hh++];
get(hh);
for(auto e:g[u]){
auto[v,w]=e;
int dist=dis[u]+w;
if(dis[v]>dist){
dis[v]=dist;
if(w)q[tt++]=v,get(tt);
else --hh,get(hh),q[hh]=v;
}
}
}
printf("%d",dis[m]==0x3f3f3f3f?-1:dis[m]-1);
return 0;
}