立下flag：今天一定AC这道题！

题目意思：

思路：

然而并没有分。。

输出-1，祈求CCF的施舍（

30% 的数据，有 \(s_1 = s_2\)

求 1 号点到 \(s_1\) 最短路，再计算不需要的路径。
SPFA，启动！

#include<bits/stdc++.h>

using namespace std;

const int maxn=3010;
const int maxm=3010;

int m,n;
int s1,t1,s2,t2;
int en;
int fir[maxn];

struct edge{
	int v;
	int next;
}ed[maxm*2];

void add_edge(int u,int v)
{
	en++;
	ed[en].v=v;
	ed[en].next=fir[u];
	fir[u]=en;
}

queue<int>q;
int dist[maxn];
bool inque[maxn];

void spfa(int r)
{
	memset(dist,0x3f3f3f,sizeof(dist));
	dist[r]=0;
	q.push(r);
	inque[r]=true;
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for(int i=fir[now];i;i=ed[i].next)
		{
			int p=ed[i].v;
			if(dist[p]>dist[now]+1){
				dist[p]=dist[now]+1;
				if(inque[p]==false){
					inque[p]=true;
					q.push(p);
				}
			}
		}
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		add_edge(u,v);add_edge(v,u);//无向图 
	 }
	cin>>s1>>t1>>s2>>t2;
	spfa(1);
	cout<<m-dist[s1]<<endl;
	return 0; 
}

居然多了5分，35分直接拿下！

发现最佳情况一定是这样（如图）

当 \(a+b+c\) 的值最小的时候，方案是最优的，此时答案就是 \(m-(a+b+c)\)
那么我们就要找出这个 n
先算出 1、s1、s2这三个点分别到其余点的最短路，然后枚举 i 寻找最小值。

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=3010;
const int maxm=3010;
int ans=LLONG_MAX;

int m,n;
int s1,t1,s2,t2;
int en;
int fir[maxn];

struct edge{
	int v;
	int next;
}ed[maxm*2];

void add_edge(int u,int v)
{
	en++;
	ed[en].v=v;
	ed[en].next=fir[u];
	fir[u]=en;
}

queue<int>q;
int dist[4][maxn];
bool inque[maxn];

void spfa(int w,int r)
{
	for(int i=1;i<=n;i++)
	{
		dist[w][i]=0x3f3f3f;
	}
	dist[w][r]=0;
	q.push(r);
	inque[r]=true;
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for(int i=fir[now];i;i=ed[i].next)
		{
			int p=ed[i].v;
			if(dist[w][p]>dist[w][now]+1){
				dist[w][p]=dist[w][now]+1;
				if(inque[p]==false){
					inque[p]=true;
					q.push(p);
				}
			}
		}
	}
}

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		add_edge(u,v);add_edge(v,u);//无向图 
	 }
	cin>>s1>>t1>>s2>>t2;
	spfa(1,1);
	spfa(2,s1);
	spfa(3,s2);
	for(int i=1;i<=n;i++)
	{
		if(dist[1][i]+dist[2][i]<=t1&&dist[1][i]+dist[3][i]<=t2)
			ans=min(ans,dist[1][i]+dist[2][i]+dist[3][i]);
	}
	if(ans==LLONG_MAX) cout<<-1<<endl;
	else cout<<m-ans<<endl;
	return 0; 
}

但是这样居然只有95！？

一定要把inque数组清零！！！！

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=3010;
const int maxm=3010;
int ans=LLONG_MAX;

int m,n;
int s1,t1,s2,t2;
int en;
int fir[maxn];

struct edge{
	int v;
	int next;
}ed[maxm*2];

void add_edge(int u,int v)
{
	en++;
	ed[en].v=v;
	ed[en].next=fir[u];
	fir[u]=en;
}

queue<int>q;
int dist[4][maxn];
bool inque[maxn];

void spfa(int w,int r)
{
	for(int i=1;i<=n;i++)
	{
		dist[w][i]=0x3f3f3f;
	}
	memset(inque,false,sizeof(inque));
	dist[w][r]=0;
	q.push(r);
	inque[r]=true;
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for(int i=fir[now];i;i=ed[i].next)
		{
			int p=ed[i].v;
			if(dist[w][p]>dist[w][now]+1){
				dist[w][p]=dist[w][now]+1;
				if(inque[p]==false){
					inque[p]=true;
					q.push(p);
				}
			}
		}
	}
}

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		add_edge(u,v);add_edge(v,u);//无向图 
	 }
	cin>>s1>>t1>>s2>>t2;
	spfa(1,1);
	spfa(2,s1);
	spfa(3,s2);
	for(int i=1;i<=n;i++)
	{
		if(dist[1][i]+dist[2][i]<=t1&&dist[1][i]+dist[3][i]<=t2)
			ans=min(ans,dist[1][i]+dist[2][i]+dist[3][i]);
	}
	if(ans==LLONG_MAX) cout<<-1<<endl;
	else cout<<m-ans<<endl;
	return 0; 
}

简单捏~