思路：这么菜的题我居然想了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 = 3000 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 + 7; 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] = 0; 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] + 1; 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, -1, sizeof(d)); scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); edge[u].push_back(v); edge[v].push_back(u); } for(int i = 1; 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 0; } int ans = d[s1][t1] + d[s2][t2]; for(int u = 1; u <= n; u++) { for(int v = 1; v <= n; v++) { ans = min(ans, cal(u, v)); } } printf("%d ", m - ans); return 0; } /* */