【NOIP模拟赛】图

题解：
这道题先考虑会有几种情况，显然只有两种对吧1ab一组cd一组2全部一组，那么我们就先跑n遍bfs那么就可以求出任意两点间距离，然后呢就枚举ab和cd两组间重合长度，重合就可以减去嘛

#include<bits/stdc++.h>
using namespace std;
int n,m;
int tot,inf;
int ver[6005];
int head[6005];
int next[6005];
int vis[3005];
int f[3005][3005];
int a,b,c,d;
int read() {
	int num=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0') {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		num=(num<<3)+(num<<1)+ch-'0';
		ch=getchar();
	}
	return num;
}
void add(int x,int y) {
	ver[++tot]=y;
	next[tot]=head[x];
	head[x]=tot;
}
void bfs(int u) {
	for(int i=1; i<=n; i++) {
		vis[i]=0;
	}
	queue<int>q;
	while(q.size()) q.pop();
	q.push(u);
	vis[u]=1;
	while(q.size()) {
		int x=q.front();
		q.pop();
		for(int i=head[x]; i; i=next[i]) {
			if(!vis[ver[i]]) {
				vis[ver[i]]=1;
				q.push(ver[i]);
				f[u][ver[i]]=f[u][x]+1;
			}
		}
	}
}
int work(int x,int l,int r) {
	return min(f[x][l],f[x][r]);
}
int main() {
	n=read(),m=read();
	a=read(),b=read(),c=read(),d=read();
	for(int i=1; i<=m; i++) {
		int x=read(),y=read();
		add(x,y);
		add(y,x);
	}
	for(int i=1; i<=n; i++) bfs(i);
	int ans=f[a][b]+f[c][d];
	for(int i=1; i<=n; i++) {
		for(int j=i+1; j<=n; j++) {
			ans=min(ans,work(a,i,j)+work(b,i,j)+work(c,i,j)+work(d,i,j)+f[i][j]);
		}
	}
	printf("%d",ans);
}