1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
using namespace std;
const int maxn = 3010;
int d[maxn][maxn];
int n, m;
bool vis[maxn];
vector<int> G[maxn];
void (int s){
memset(vis, 0, sizeof(vis));
queue<int> q;
q.emplace(s);
vis[s] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
for(auto &v : G[u]){
if(vis[v]) continue;
d[s][v] = d[s][u] + 1;
vis[v] = 1;
q.emplace(v);
}
}
}
int s1, t1, l1, s2, t2, l2;
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
for(int i = 1; i <= n; i++){
bfs(i);
}
cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
if(d[s1][t1] > l1 || d[s2][t2] > l2){
cout << -1 << 'n';
return 0;
}
int res = d[s1][t1] + d[s2][t2];
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
if(d[s1][i] + d[i][j] + d[j][t1] <= l1 && d[s2][i] + d[i][j] + d[j][t2] <= l2)
res = min(res, d[s1][i] + d[j][t1] + d[s2][i] + d[j][t2] + d[i][j]);
if(d[s1][j] + d[i][j] + d[i][t1] <= l1 && d[s2][i] + d[i][j] + d[j][t2] <= l2)
res = min(res, d[s1][j] + d[i][t1] + d[s2][i] + d[j][t2] + d[i][j]);
if(d[s1][j] + d[i][j] + d[i][t1] <= l1 && d[s2][j] + d[i][j] + d[i][t2] <= l2)
res = min(res, d[s1][j] + d[i][t1] + d[s2][j] + d[i][t2] + d[i][j]);
if(d[s1][i] + d[i][j] + d[j][t1] <= l1 && d[s2][j] + d[i][j] + d[i][t2] <= l2)
res = min(res, d[s1][i] + d[j][t1] + d[s2][j] + d[i][t2] + d[i][j]);
}
}
cout << m - res << 'n';
return 0;
}
|
近期评论