Untitled

 avatar
unknown
plain_text
2 years ago
1.7 kB
7
Indexable
 /** In The Name Of God **/
#include <bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(v) v.begin(), v.end()
#define pb push_back

typedef long long ll;

vector <int> adj[3010];
int dis[3010][3010];

void solve()
{
    /// input
    int n, m; cin >> n >> m;
    for (int i=0; i<m; i++){
        int a, b; cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    int s[2], t[2], l[2];
    for (int i=0; i<2; i++) cin >> s[i] >> t[i] >> l[i];

    /// find dis between all two vertices
    for (int i=1; i<=n; i++){
        queue <int> q;
        q.push(i);
        dis[i][i] = 0;
        while (!q.empty()){
            int x = q.front();
            q.pop();
            for (auto v : adj[x]){
                if (dis[i][v] == 0){
                    dis[i][v] = dis[i][x] + 1;
                    q.push(v);
                }
            }
        }
    }

    /// find answer
    int ans = 1e4;
    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            int x = dis[s[0]][i] + dis[i][j] + dis[j][t[0]];
            int y = dis[s[1]][i] + dis[i][j] + dis[j][t[1]];
            if (x <= l[0] && y <= l[1]) ans = min(ans , x + y - dis[i][j]);
        }
    }
    int x = dis[s[0]][t[0]];
    int y = dis[s[1]][t[1]];
    if (x <= l[0] && y <= l[1]) ans = min(ans , x + y);
    /// output
    if (ans > m) cout << "-1";
    else cout << m - ans;
}
int main()
{
    int t = 1; /// cin >> t;
    while (t--) solve();
}
 /**
    Life can only be understood backwards;
        but it must be lived forwards;
**/
Editor is loading...