题意：
给定一个n个点（n<=3000）所有边长为1的图，求最多可以删掉多少条边后，图满足s1到t1的距离小于l1，s2到t2的距离小于l2。
Solution：
首先可以分两种情况讨论：
1：假设最后留下的边是互不相交的两条路径。此时的答案是n-s1到t1的最短路径-s2到t2的最短路径。
2：假设最后留下的边有重合的一段，此时只要枚举重合的这一段的起点和终点，就可以判断。注意此时要考虑这两条路径经过枚举的两点的顺序。
限制的条件比较多，可以用来剪枝的条件也很多。
由于所有边的长度为1，用DFS或者SPFA算法可以很快地求出最短路。
#include <bits/stdc++.h>
using namespace std; const int N = ; struct edge {
int v, ne;
} E[N * N << ];
int head[N], cnt; int n, m, ans;
int s1, s2, t1, t2, l1, l2; int dis[][N];
int vis[N]; void SPFA (int S, int k) {
queue<int> q;
memset (vis, , sizeof vis);
dis[k][S] = ;
vis[S] = ;
q.push (S);
while (!q.empty() ) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = E[i].ne) {
int v = E[i].v;
if (dis[k][u] + < dis[k][v]) {
dis[k][v] = dis[k][u] + ;
if (!vis[v]) {
vis[v] = ;
q.push (v);
}
}
}
vis[u] = ;
}
} inline void add (int u, int v) {
E[++cnt].v = v, E[cnt].ne = head[u];
head[u] = cnt;
} int main() {
ios::sync_with_stdio ();
cin >> n >> m;
for (int i = , u, v; i <= m; ++i) {
cin >> u >> v;
add (u, v), add (v, u);
}
cin >> s1 >> t1 >> l1;
cin >> s2 >> t2 >> l2;
memset (dis, 0x1f, sizeof dis);
SPFA (s1, );
SPFA (s2, );
SPFA (t1, );
SPFA (t2, );
if (dis[][t1] <= l1 && dis[][t2] <= l2) {
ans = dis[][t1] + dis[][t2];
for (int i = ; i <= n; ++i) {
int flag = ;
for (int k = ; k <= n; ++k) dis[][k] = ;
for (int j = i + ; j <= n; ++j) {
int tem1 = min (dis[][i] + dis[][j], dis[][j] + dis[][i]);
int tem2 = min (dis[][i] + dis[][j], dis[][j] + dis[][i]);
if (tem1 + tem2 < ans && tem1 < l1 && tem2 < l2) {
if (!flag) {
SPFA (i, );
flag = ;
}
if (tem1 + dis[][j] <= l1 && tem2 + dis[][j] <= l2) {
ans = min (ans, tem1 + tem2 + dis[][j]);
}
}
}
}
}
else {
ans = m + ;
}
cout << m - ans << endl;
}