Jzoj3155 最短路

N 个结点、M 个含K 个结点的完全子图构成一个奇怪的图，问从结点1 走到结点N 最少需要经过多少个结点。

非常经典的套路了，当时做2sat也讲过了

建立中转站让后直接bfs，最后距离/2就好

#pragma GCC opitmize("O3")
#pragma G++ opitmize("O3")
#include<queue>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 100000
using namespace std;
vector<int> G[101010];
int d[101010],n,m,k; queue<int> q;
int main(){
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=m;++i)
		for(int x,j=1;j<=k;++j){
			scanf("%d",&x);
			G[x].push_back(i+N);
			G[i+N].push_back(x);
		}
	memset(d,-1,sizeof d); d[1]=2; q.push(1);
	for(int x;!q.empty() && d[n]<0;q.pop()){
		x=q.front();
		for(int v,i=0,z=G[x].size();i<z;++i)
			if(d[v=G[x][i]]<0){ d[v]=d[x]+1; q.push(v); }
	}
	if(d[n]<0) puts("-1"); else printf("%d
",d[n]>>1);
}