刷题记录表

#include<bits/stdc++.h>
using namespace std;
inline int read(int &a){a=0;int f=1;char c=getchar();if(c==EOF) return a=EOF;
for(;c<'0' || c>'9';c=getchar()){if(c=='-') f=-1;if(c==EOF) return a=EOF;}
for(;c<='9' && c>='0';a=a*10+c-'0',c=getchar());return a*=f;}
inline void print(int a){int s[20],t=0;if(!a){putchar('0');putchar('\n');return;}
if(a<0) a=-a,putchar('-');while(a){s[t++]=a%10,a/=10;}
for(;t--;putchar(s[t]+'0'));putchar('\n');}
int n,m;
struct tree{
	int next,ver;
} e[10010];
int head[3010],tot;
void add(int a,int b){e[++tot].next=head[a],head[a]=tot,e[tot].ver=b;
e[++tot].next=head[b],head[b]=tot,e[tot].ver=a;}
int s1,t1,l1,s2,t2,l2;
int bj[3010];
int f[3010][3010];
int ans;
struct duilie{
	int a[10010];
	int head,tail;
	bool end(){return head==tail;}
	void add(int x){a[tail++]=x;}
	int top(){return a[head];}
	void pop(){head++;}
	void clear(){head=tail=0;}
} q;

int main()
{
	freopen("roads.in","r",stdin);
	freopen("roads.out","w",stdout);
	read(n),read(m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		read(a),read(b);
		add(a,b);
	}
	read(s1),read(t1),read(l1);
	read(s2),read(t2),read(l2);
	for(int i=1;i<=n;i++)
	{
		q.clear();
		q.add(i);
		bj[i]=i;
		while(!q.end())
		{
			int x=q.top();
			q.pop();
//			cout<<x<<endl;
			for(int j=head[x];j;j=e[j].next)
			if(bj[e[j].ver]!=i)
			{
				bj[e[j].ver]=i;
				f[i][e[j].ver]=f[i][x]+1;
				q.add(e[j].ver);
			}
		}
	}
	ans=m-f[s1][t1]-f[s2][t2];
	if(f[s1][t1]>l1 || f[s2][t2]>l2)
	{
		puts("-1");
		return 0;
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(i!=j && f[s1][i]+f[i][j]+f[j][t1]<=l1)
	{
		if(f[s2][i]+f[i][j]+f[j][t2]<=l2)
		ans=max(ans,m-f[s1][i]-f[s2][i]-f[i][j]-f[j][t1]-f[j][t2]);
        if(f[t2][i]+f[i][j]+f[j][s2]<=l2)
		ans=max(ans,m-f[s1][i]-f[t2][i]-f[i][j]-f[j][t1]-f[j][s2]);
	}
	printf("%d\n",ans);
	return 0;
}