Untitled
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...