543B - Destroying Roads - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

const int maxn = 3010;
int n, m, s1, t1, l1, s2, t2, l2;
vector<int>adj[maxn];
int dis[maxn][maxn];
queue<int> q;


void input()
{
	cin >> n >> m;
	int a, b;
	for(int i = 1; i <= m; i++)
	{
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	cin >> s1 >> t1 >> l1;
	cin >> s2 >> t2 >> l2;
}

void bfs(int r)
{
	q.push(r);
	while(!q.empty())
	{
		int v = q.front();
		for(int i = 0; i < adj[v].size(); i++)
		{
			int u = adj[v][i];
			if(dis[r][u] > 0 || u == r)
			{
				continue;
			}
			dis[r][u] = dis[r][v]+1;
			q.push(u);
		}
		q.pop();
	}
}

int main()
{
	input();
	for(int i = 1; i <= n; i++)
	{
		bfs(i);
	}
	if(dis[s1][t1] > l1 || dis[s2][t2] > l2)
	{
		cout << -1 << endl;
		return 0;
	}
	int ans = dis[s1][t1] + dis[s2][t2];
//	cout << ans << endl;
//	cout << "6-4 : " << dis[6][4] << endl << "4-3 : " << dis[4][3] << endl << "3-2 : " << dis[3][2] << endl;
	for(int u = 1; u <= n; u++)
	{
		for(int v = 1; v <= n; v++)
		{
			int a = dis[s1][u] + dis[u][v] + dis[v][t1];
			a = min(a, dis[s1][v] + dis[u][v] + dis[u][t1]);
			int b = dis[s2][u] + dis[u][v] + dis[v][t2];
			b = min(b, dis[s2][v] + dis[u][v] + dis[u][t2]);
			if(a > l1 || b > l2)
				continue;
			a += b - dis[u][v];
			if(ans > a)
			{
			//	cout << u << " , " << v << " : " << a << endl;
				ans = a;
			}
		}
	}
	cout << m - ans << endl;
}