欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【NOIP模拟赛】图

程序员文章站 2023-12-26 10:03:27
...

【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);
}

上一篇:

下一篇: