题目地址：Codeforces：Problem – 666B – Codeforces、洛谷：【CF666B】World Tour – 洛谷

题目描述

In some country there are exactly n cities and m bidirectional roads connecting the cities. Cities are numbered with integers from 1 to n. If cities a and b are connected by a road, then in an hour you can go along this road either from city a to city b, or from city b to city a. The road network is such that from any city you can get to any other one by moving along the roads.
You want to destroy the largest possible number of roads in the country so that the remaining roads would allow you to get from city s1 to city t1 in at most l1 hours and get from city s2 to city t2 in at most l2 hours.
Determine what maximum number of roads you need to destroy in order to meet the condition of your plan. If it is impossible to reach the desired result, print -1.
求最多能删去的边数，且删去后满足dis[s1][t1]<=l1，dis[s2][t2]<=l2。

输入输出格式

输入格式：
The first line contains two integers n, m (1 ≤ n ≤ 3000, n - 1 \leq m \leq \min\{3000, \frac{n(n-1)}{2}\}) — the number of cities and roads in the country, respectively.
Next m lines contain the descriptions of the roads as pairs of integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi). It is guaranteed that the roads that are given in the description can transport you from any city to any other one. It is guaranteed that each pair of cities has at most one road between them.
The last two lines contains three integers each, s1, t1, l1 and s2, t2, l2, respectively (1 ≤ si, ti ≤ n, 0 ≤ li ≤ n).

输出格式：
Print a single number — the answer to the problem. If the it is impossible to meet the conditions, print -1.

输入输出样例

输入样例#1：

5 4
1 2
2 3
3 4
4 5
1 3 2
3 5 2

输出样例#1：

0

输入样例#2：

5 4
1 2
2 3
3 4
4 5
1 3 2
2 4 2

输出样例#2：

1

输入样例#3：

5 4
1 2
2 3
3 4
4 5
1 3 2
3 5 1

输出样例#3：

-1

题解

首先BFS预处理出所有点之间的最短路。如果dis[s1][t1]和dis[s2][t2]没删边就已经不满足了那删边是没有用的，这种情况就是无解的情况。
接着考虑在原本的最短路上有什么方法可以使最短路覆盖的边数减少。我们可以让两条路径中间有一段重合，兴许能减少边数。为什么是一段？因为如果有多段重合，把多段重合之间没重合的改成重合的显然更优。这样我们枚举重合的一段的端点，并且计算总长，更新答案。需要注意的是，s1/s2→u→v→t1/t2与s1→u→v→t1/s2→v→u→t2这两种情况都要考虑，因为是无向图可以双向通行嘛。
复杂度O(n^2)。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <vector>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 3005;

int n, m, ut, vt, s1, t1, l1, s2, t2, l2, dis[MAXN][MAXN], ans;
bool vis[MAXN];
std::vector<int> gra[MAXN];
std::queue<int> que;

inline void bfs(int st) {
    int *dist = dis[st];
    memset(vis, 0, sizeof(vis));
    que.push(st);
    vis[st] = true;
    dist[st] = 0;
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        for(int v : gra[u]) {
            if(vis[v]) continue;
            vis[v] = true; 
            dist[v] = dist[u] + 1;
            que.push(v);
        }
    }
}

inline void updateans(int u, int v) {
    int c1 = dis[s1][u] + dis[u][v] + dis[v][t1], c2 = dis[s2][u] + dis[u][v] + dis[v][t2], c = c1 + c2 - dis[u][v];
    if(c1 <= l1 && c2 <= l2) ans = std::min(ans, c);
    c2 = dis[s2][v] + dis[u][v] + dis[u][t2], c = c1 + c2 - dis[u][v];
    if(c1 <= l1 && c2 <= l2) ans = std::min(ans, c);
}

int main() {
    memset(dis, 0x3f, sizeof(dis));
    n = readint(), m = readint();
    for(int i = 1; i <= m; i++) {
        ut = readint(), vt = readint();
        gra[ut].push_back(vt);
        gra[vt].push_back(ut);
    }
    s1 = readint(), t1 = readint(), l1 = readint();
    s2 = readint(), t2 = readint(), l2 = readint();
    for(int i = 1; i <= n; i++) {
        bfs(i);
    }
    if(dis[s1][t1] > l1 || dis[s2][t2] > l2) {
        printf("-1");
        return 0;
    }
    ans = dis[s1][t1] + dis[s2][t2];
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            updateans(i, j);
        }
    }
    printf("%d", m - ans);
    return 0;
}