90分求助TUT
查看原帖
90分求助TUT
1030687
coco20121120楼主2024/10/22 16:11

请问哪位大佬能指点一下

#include<bits/stdc++.h>
using namespace std;
int f[3005][3005],s[3005],p[3005],l[3005];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	memset(f,0,sizeof(f));
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		f[a][b]=1,f[b][a]=1;
	}
	memset(s,127,sizeof(s));
	memset(p,0,sizeof(p));
	s[1]=0;
	int u=1;
	while(u!=n){
		int minn=1e9,t=0;
		for(int i=1;i<=n;i++)
			if(p[i]!=1&&s[i]<minn) minn=s[i],t=i;
		p[t]=1;
		for(int i=1;i<=n;i++)
			if(f[t][i]!=0&&p[i]!=1)
				if(minn+1<s[i]) s[i]=minn+1,l[i]=t;
		u++;
	}
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	if(s[a]>b||s[c]>d) printf("-1");
	else{
		int x1=a,ans=s[a]+s[c];
		while(x1!=1){
			int x2=c;
			while(x2!=1){
				if(x1==x2&&l[x1]==l[x2]) ans--;
				x2=l[x2];
			}
			x1=l[x1];
		}
		printf("%d",m-ans);
	}
	return 0;
}

谢谢~

2024/10/22 16:11
加载中...