Codeforces Round #302 (Div. 1) B - Destroying Roads

B - Destroying Roads

思路：这么菜的题我居然想了40分钟。。。 n^2枚举两个交汇点，点与点之间肯定都跑最短路，取最小值。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define y1 skldjfskldjg

#define y2 skldfjsklejg

using namespace std;

const int N =  + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

int d[N][N], n, m, s1, t1, l1, s2, t2, l2;

vector<int> edge[N];

void Dij(int S, int d[N]) {

    queue<int> que;

    d[S] = ; que.push(S);

    while(!que.empty()) {

       int u = que.front(); que.pop();

       for(int v : edge[u]) {

            if(~d[v]) continue;

            d[v] = d[u] + ;

            que.push(v);

       }

    }

}

int cal(int u, int v) {

    int ret1 = min(d[s1][u] + d[t1][v], d[t1][u] + d[s1][v]);

    int ret2 = min(d[s2][u] + d[t2][v], d[t2][u] + d[s2][v]);

    if(ret1 + d[u][v] > l1 || ret2 + d[u][v] > l2) return inf;

    return d[u][v] + ret1 + ret2;

}

int main() {

    memset(d, -, sizeof(d));

    scanf("%d%d", &n, &m);

    for(int i = ; i <= m; i++) {

        int u, v;

        scanf("%d%d", &u, &v);

        edge[u].push_back(v);

        edge[v].push_back(u);

    }

    for(int i = ; i <= n; i++) Dij(i, d[i]);

    scanf("%d%d%d%d%d%d", &s1, &t1, &l1, &s2, &t2, &l2);

    if(d[s1][t1] > l1 || d[s2][t2] > l2) {

        puts("-1");

        return ;

    }

    int ans = d[s1][t1] + d[s2][t2];

    for(int u = ; u <= n; u++) {

        for(int v = ; v <= n; v++) {

            ans = min(ans, cal(u, v));

        }

    }

    printf("%d\n", m - ans);

    return ;

}

/*

*/

Codeforces Round #302 (Div. 1) B - Destroying Roads的相关教程结束。